시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 2 2 50.000%

문제

이비카는 근처 공원에서 산책을 하기로 마음먹었다. 그 공원은 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과 가운데 분수를 연결하는 길의 사용 가능 여부로 시작한다.

출력

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

예제 입력

6
111011
001101

예제 출력

3

힌트