#8963. 「洛谷 P12057」[THUPC 2025 决赛] 好串 暂未评定

对于三个长度为 的 01 字符串 ，称长度为 的 01 字符串 是好的当且仅当 。设 为这样的好的串的数量。

现在我们有三个长度为 的随机 01 字符串 ，其中 的第 个字符有 的概率为 1， 的概率为 0，其中 是一个 至 的整数。所有的随机事件是独立的。你需要求 的期望，对 取模。

输入第一行一个整数 表示字符串长度，接下来一个 行 列的数字矩阵，其中第 行第 列的字符表示 。

输出一个整数表示答案对 取模的值。

样例输入 1

复制3
900
090
009

样例输出 1

复制4

样例输入 2

复制3
999
999
999

样例输出 2

复制1

样例输入 3

复制10
0123456789
1234567890
2345678901

样例输出 3

复制612360617

样例 #1 解释

在该组样例中， 分别为 100, 010, 001，四种方案分别为 100、010、001、000。

来源与致谢

来自 THUPC2025（2025 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 https://thusaac.com/public。