The Central Europe Regional Contest (CERC) is a competition famous for its interesting and well-prepared problems. One such problem* involved finding the volume of the union of three spheres, i.e., the set of points belonging to at least one of these spheres. This might have been a challenge 10 years ago, but nowadays, we should not bore contestants with something so easy and standard. Instead of a three-dimensional space, let us use an $n$-dimensional hypercube. This, of course, requires some definitions.

An $n$-dimensional hypercube has $2^n$ vertices, each described by a sequence of $n$ coordinates of 0 and 1. For example, a three-dimensional hypercube has 8 vertices: 000, 001, 010, 011, 100, 101, 110, 111.

A hyperball with radius $r$ and center $s$ is the set of vertices of the hypercube that are at a distance of at most $r$ from vertex $s$. We calculate the distance using the Manhattan metric; therefore, a vertex $p$ belongs to a hyperball with radius $r$ and center $s$ if and only if the coordinates of vertices $p$ and $s$ differ in at most $r$ positions.

Find the number of vertices that belong to the union of three given hyperballs, i.e., the number of vertices belonging to at least one of them. Output the result modulo $10^9 + 7$.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 10\,000$), representing the number of dimensions.

The description of the hyperballs is provided in the next three lines: the $i$-th of these lines contains an integer $r_i$ ($0 \le r_i \le n$) and a binary string $s_i$ consisting of $n$ characters 0 and 1. These are the radius and center of the $i$-th hyperball, respectively.

Output

Output a single integer — the number of vertices belonging to the union of the three hyperballs, modulo $10^9 + 7$.

Examples

Input 1

3
1 000
1 100
0 111

Output 1

7

Input 2

5
2 10110
0 11010
1 00000

Output 2

19

Note

Explanation of the first example: A three-dimensional hypercube is simply a cube. The drawings below show the vertices that belong to the individual hyperballs. The gray circle denotes the center of the hyperball.

The first hyperball contains vertices 000, 100, 010, 001. The second contains vertices 100, 000, 110, 101. The third is the single vertex 111. The union of the hyperballs contains 7 vertices — all except 011.

Subtasks

There is at least one group of tests where $r_i \le 500$. There is also at least one group of tests where each contains at least two identical hyperballs (the same radius and center).

*CERC 2009, problem E: http://cepc09.ii.uni.wroc.pl/lost2.pdf