Park Walk

Ivica decides to take a walk in a nearby park. The park has N+1 fountains. The largest fountain is at the center of the park, and the other N fountains are arranged in a circle around it. The outer fountains are numbered from 1 to N, and the central fountain is numbered N+1.

The outer fountains are connected to each other by roads forming a circle, and each outer fountain is also connected to the central fountain. In total, there are 2*N roads.

Some roads are being cleaned by volunteers and are usually unavailable.

The figure above shows a park with N=6. In this figure, every road is available.

This is the same park as in the first figure, but some roads are unavailable.

Ivica starts his walk near any fountain. He does not want to visit the same fountain twice or use the same road twice. The walk ends when he returns to the fountain where he started.

Write a program that computes the number of different walking routes Ivica can take. Two routes are different if they do not contain exactly the same set of roads. Therefore, the starting fountain and the order in which the roads are traveled do not matter. In the second figure above, there are three routes: 1-2-3-7-6-1, 1-2-3-7-4-5-6-1, and 4-5-6-7-4.

The first line contains an integer N, the number of outer fountains (2 ≤ N ≤ 100000).

The second and third lines each contain a string consisting of 0 and 1. A 0 means the corresponding road is unavailable, and a 1 means it is available.

The string on the second line describes the availability of the outer roads connecting adjacent outer fountains. The roads are listed counterclockwise, starting with the road connecting fountains N and 1.

The string on the third line describes the availability of the inner roads connecting outer fountains to the central fountain. The roads are listed counterclockwise, starting with the road connecting fountain 1 to the central fountain.

Print the number of possible walking routes.