공원 산책

이비카는 근처 공원을 산책하려고 한다. 이 공원에는 N+1개의 분수가 있다. 가장 큰 분수는 공원 중앙에 있고, 나머지 N개의 분수는 중앙 분수를 둘러싸며 원형으로 배치되어 있다. 바깥쪽 분수에는 1부터 N까지의 번호가 붙어 있고, 중앙 분수의 번호는 N+1이다.

바깥쪽 분수들은 원을 이루는 길로 서로 연결되어 있으며, 각 바깥쪽 분수는 중앙 분수와도 연결되어 있다. 길은 모두 2*N개이다.

일부 길은 자원봉사자들이 청소 중이라 보통 사용할 수 없다.

위 그림은 N=6인 공원을 나타낸다. 이 그림에서는 모든 길을 사용할 수 있다.

이는 첫 번째 그림과 같은 공원이지만, 몇몇 길을 사용할 수 없는 경우이다.

이비카는 임의의 분수 근처에서 산책을 시작한다. 그는 같은 분수를 두 번 방문하거나 같은 길을 두 번 사용하고 싶어 하지 않는다. 산책은 시작한 분수에 다시 도착했을 때 끝난다.

이비카가 할 수 있는 산책 경로의 수를 구하는 프로그램을 작성하라. 두 경로가 포함하는 길의 집합이 완전히 같지 않으면 서로 다른 경로이다. 따라서 시작 분수와 길을 지나는 순서는 고려하지 않는다. 위의 두 번째 그림에서는 1-2-3-7-6-1, 1-2-3-7-4-5-6-1, 4-5-6-7-4의 세 가지 경로가 있다.

첫째 줄에 바깥쪽 분수의 개수인 정수 N(2 ≤ N ≤ 100000)이 주어진다.

둘째 줄과 셋째 줄에는 각각 0과 1로 이루어진 문자열이 주어진다. 0은 해당 길을 사용할 수 없음을, 1은 사용할 수 있음을 뜻한다.

둘째 줄의 문자열은 서로 이웃한 바깥쪽 분수들을 연결하는 바깥쪽 길의 사용 가능 여부를 나타낸다. 길은 반시계 방향 순서로 주어지며, 분수 N과 1을 연결하는 길부터 시작한다.

셋째 줄의 문자열은 바깥쪽 분수와 중앙 분수를 연결하는 안쪽 길의 사용 가능 여부를 나타낸다. 길은 반시계 방향 순서로 주어지며, 분수 1과 중앙 분수를 연결하는 길부터 시작한다.

가능한 산책 경로의 수를 출력하라.