Central Europe Regional Contest (CERC) 以其有趣且准备充分的题目而闻名。其中一道题目是求三个球体并集的体积，即属于至少一个球体的点集。这在 10 年前可能是一个挑战，但在今天，用如此简单且标准的问题来让选手感到无聊是不合适的。因此，我们不再使用三维空间，而是使用 $n$ 维超立方体。这当然需要一些定义。

$n$ 维超立方体有 $2^n$ 个顶点，每个顶点由一个包含 $n$ 个 0 和 1 的坐标序列描述。例如，三维超立方体有 8 个顶点：000, 001, 010, 011, 100, 101, 110, 111。

半径为 $r$、中心为 $s$ 的超球体是超立方体中与顶点 $s$ 的距离不超过 $r$ 的所有顶点的集合。距离采用曼哈顿距离计算，因此顶点 $p$ 属于半径为 $r$、中心为 $s$ 的超球体，当且仅当顶点 $p$ 和 $s$ 的坐标在不超过 $r$ 个位置上不同。

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

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 10\,000$)，表示维数。 接下来的三行描述了超球体：第 $i$ 行包含一个整数 $r_i$ ($0 \le r_i \le n$) 和一个由 $n$ 个 0 和 1 组成的二进制字符串 $s_i$，分别表示第 $i$ 个超球体的半径和中心。

输出格式

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

样例

样例 1

输入：

3
1 000
1 100
0 111

输出：

7

样例 2

输入：

5
2 10110
0 11010
1 00000

输出：

19

说明

第一个样例的解释：三维超立方体就是一个立方体。下图展示了属于各个超球体的顶点。灰色圆圈表示超球体的中心。

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

子任务

至少有一组测试数据满足 $r_i \le 500$。此外，至少有一组测试数据包含至少两个相同的超球体（相同的半径和中心）。