中欧区域赛 (CERC) 以其有趣且准备充分的题目而闻名。其中一道题目是关于求三个球体并集的体积。这在 10 年前可能是一个挑战，但如今选手们不应再被如此简单且标准的题目所困扰。我们不再使用三维空间，而是使用 $n$ 维超立方体。显然，这需要一些定义。

$n$ 维超立方体有 $2^n$ 个顶点，每个顶点由一个长度为 $n$ 的坐标序列表示，坐标值均为 0 或 1。例如，3 维超立方体有 8 个顶点：000, 001, 010, 011, 100, 101, 110, 111。

半径为 $r$、中心为 $s$ 的球体是超立方体中到顶点 $s$ 的距离不超过 $r$ 的顶点子集。我们使用曼哈顿距离计算距离，这意味着当且仅当顶点 $p$ 和 $s$ 的坐标在不超过 $r$ 个位置上不同时，顶点 $p$ 属于该球体。

求属于这三个球体并集的顶点数量，即属于至少其中一个球体的顶点数量。输出结果对 $10^9 + 7$ 取模。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10\,000$)，表示维度数。

接下来是三个球体的描述。每个描述占一行，第 $i$ 行包含一个整数 $r_i$ ($0 \le r_i \le n$) 和一个由 $n$ 个 0 或 1 组成的二进制字符串 $s_i$，分别表示球体的半径和中心。

输出格式

输出一个整数，表示属于这三个球体并集的顶点数量，对 $10^9 + 7$ 取模。

样例

样例输入 1

3
1 000
1 100
0 111

样例输出 1

7

样例输入 2

5
2 10110
0 11010
1 00000

样例输出 2

19

说明

第一个样例的解释：3 维超立方体就是一个普通的立方体。下图展示了哪些顶点属于对应的球体。灰色圆圈表示球体的中心。

第一个球体包含顶点 000, 100, 010, 001。第二个球体包含顶点 100, 000, 110, 101。第三个球体仅包含单个顶点 111。这些球体的并集包含 7 个顶点——除了 011 之外的所有顶点。