Lake

Time limit1sMemory limit128 MB

Summary

Count simple cycles in a fixed circular ladder graph with some edges removed, given three binary strings of usable inner, outer, and bridge edges, modulo 1e9+7.

Level: Medium7 of 10
Topics: Graph, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

Ivica wants to take a walk in a nearby park. The park has a small lake, and there is an island in the middle of the lake. On the island, N fountains are arranged in a circle and connected by paths. Along the outer edge of the lake, another N fountains are also arranged in a circle and connected by paths.

Each fountain on the island, called an inner fountain, is connected by a bridge to exactly one outer fountain. If the inner fountains are numbered 1 through N clockwise, and the outer fountains are numbered N+1 through 2·N clockwise, then there is a bridge connecting fountain F with fountain N+F.

So the park has exactly 2·N fountains and 3·N paths, counting the bridges. The left figure shows the case where every path is usable, and the right figure shows the case where some paths are unusable.



Park with N=7. Every path is usable.	The same park with some paths unusable. This state matches the first public test.

Ivica starts near some fountain. He walks along paths so that he never visits the same fountain twice and never uses the same path twice. The walk ends when he returns to the fountain where he started.

Compute the number of distinct walks Ivica can make, and output the remainder after dividing that number by 1 000 000 007. Two walks are different if they do not use exactly the same set of paths; the starting fountain and direction of traversal do not matter. In the park shown on the right, there are three possible walks: 13-6-7-14-13, 8-9-10-3-4-5-12-13-14-8, and 8-9-10-3-4-5-12-13-6-7-14-8.

Input

The first line contains an integer N (2 ≤ N ≤ 100 000), the number of inner fountains and also the number of outer fountains.

Each of the next three lines contains a string of N characters, each either 0 or 1, describing which paths are usable. A 0 means the corresponding path is unusable, and a 1 means it is usable. The three strings are given in this order:

The paths connecting the inner fountains in a cycle. They are listed clockwise, starting with the path connecting fountains N and 1.
The paths connecting the outer fountains in a cycle. They are listed clockwise, starting with the path connecting fountains 2·N and N+1.
The bridges. They are listed clockwise, starting with the bridge connecting fountains 1 and N+1.

Output

Output the number of distinct walks modulo 1 000 000 007.

Examples3

Example 1
Input
```
7
0111101
1110011
0010111
```
Expected output
```
3
```
Example 2
Input
```
8
11111111
11111111
00001000
```
Expected output
```
2
```
Example 3
Input
```
9
010111110
010111000
111101010
```
Expected output
```
4
```