호수

이비차는 근처 공원을 산책하려고 한다. 공원에는 작은 호수가 있고, 호수 가운데에는 섬이 있다. 섬에는 N개의 분수가 원형으로 놓여 있으며, 이 분수들은 길로 서로 연결되어 있다. 호수 바깥쪽 가장자리에도 N개의 분수가 원형으로 놓여 있고 길로 서로 연결되어 있다.

섬의 각 분수(안쪽 분수)는 정확히 하나의 바깥쪽 분수와 다리로 연결된다. 안쪽 분수를 시계 방향으로 1부터 N까지, 바깥쪽 분수를 시계 방향으로 N+1부터 2·N까지 번호 붙이면, 분수 F와 분수 N+F를 잇는 다리가 있다.

따라서 공원에는 모두 2·N개의 분수와 다리를 포함한 3·N개의 길이 있다. 왼쪽 그림은 모든 길을 사용할 수 있는 경우이고, 오른쪽 그림은 일부 길을 사용할 수 없는 경우이다.

N=7인 공원. 모든 길을 사용할 수 있다.	같은 공원에서 일부 길을 사용할 수 없는 모습. 첫 번째 공개 테스트와 같은 상태이다.

이비차는 어떤 분수 근처에서 산책을 시작한다. 그는 같은 분수를 두 번 방문하지 않고, 같은 길도 두 번 사용하지 않도록 길을 따라 걷는다. 산책은 처음 시작한 분수에 다시 도착하면 끝난다.

이비차가 할 수 있는 서로 다른 산책의 수를 구하고, 그 수를 1 000 000 007로 나눈 나머지를 출력하라. 두 산책이 사용하는 길의 집합이 다르면 서로 다르며, 시작 분수와 진행 방향은 구분하지 않는다. 오른쪽 그림의 공원에서는 세 가지 산책이 가능하다: 13-6-7-14-13, 8-9-10-3-4-5-12-13-14-8, 8-9-10-3-4-5-12-13-6-7-14-8.

첫째 줄에 안쪽 또는 바깥쪽 분수의 개수 N (2 ≤ N ≤ 100 000)이 주어진다.

다음 세 줄에는 길의 사용 가능 여부를 나타내는 길이 N의 0/1 문자열이 주어진다. 각 위치의 0은 해당 길을 사용할 수 없음을, 1은 사용할 수 있음을 뜻한다. 세 문자열은 다음 순서로 주어진다.

1. 안쪽 분수들을 원형으로 잇는 길. 시계 방향 순서이며, 분수 N과 1을 잇는 길부터 시작한다.
2. 바깥쪽 분수들을 원형으로 잇는 길. 시계 방향 순서이며, 분수 2·N과 N+1을 잇는 길부터 시작한다.
3. 다리. 시계 방향 순서이며, 분수 1과 N+1을 잇는 다리부터 시작한다.

서로 다른 산책의 수를 1 000 000 007로 나눈 나머지를 출력한다.