PARK

문제

Ivica has decided to take a walk in a nearby park. The park contains a total of N+1 water fountains, the largest one in the center of the park. The remaining fountains are arranged in a circle around the largest one. The surrounding fountains are numbered 1 to N and the central is marked N+1. 

The surrounding fountains are connected by paths to form a cycle. Each of the surrounding fountains is also connected to the central fountain, for a total of 2·N paths in the park. 

Some of the paths are being cleaned by volunteers and are temporarily unusable. 

[이미지 1]

Example park for N=6. All paths are usable.

[이미지 2]

Same park with some of the paths unusable. 

Ivica starts his walk near some fountain. He proceeds to use paths so that he never visits the same fountain or uses the same path twice. The walk ends when Ivica reaches the fountain where he started. 

Write a program that calculates the number of distinct walks Ivica can make. Two walks are different if they don't contain the same paths (so the starting fountain and order of traversal don't matter). For the park in the right image above, there are three walks: 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 (2 ≤ N ≤ 100 000), the number of fountains other than the central. 

Each of the following two lines contains a string of N characters '0' and '1' describing the availabilities of the paths. A zero in some position represents an unavailable path, while a one represents an available path. The two strings are: 

1. The outer paths, connecting the surrounding fountains. The paths are given in counterclockwise order, starting with the path connecting fountains N and 1. 
2. The inner paths, connecting surrounding fountains to the central one. The paths are again given in counterclockwise order, starting with the path connecting fountain 1 to the central fountain. 

출력

Output the number of distinct walks.