비트 문자열

0과 1로 이루어진 유한 수열을 비트 문자열이라고 한다. 비트 문자열 w의 길이는 w에 들어 있는 기호의 개수이다. 길이가 0인 빈 문자열도 비트 문자열이다. 비트 문자열 w의 부분 문자열은 w에서 연속한 일부이다. 빈 문자열은 모든 비트 문자열의 부분 문자열이고, 모든 비트 문자열은 자기 자신의 부분 문자열이다. 예를 들어 길이가 4인 비트 문자열 1010의 모든 부분 문자열은 1010, 101, 010, 10, 01, 1, 0, 빈 문자열이다. 비트 문자열 100과 11은 1010의 부분 문자열이 아니다. 비트 문자열 P가 비트 문자열 w의 부분 문자열이면, w가 P를 부분 문자열로 가진다고 한다.

길이가 n인 모든 비트 문자열을 생각하자. 길이가 n인 비트 문자열은 모두 2n개이다. 음이 아닌 정수 n과 두 비트 문자열 P1, P2가 주어질 때, 길이가 n이면서 P1을 부분 문자열로 가지고 P2는 부분 문자열로 가지지 않는 비트 문자열의 개수를 출력하는 프로그램을 작성하시오.

입력은 표준 입력에서 읽는다. 입력은 세 줄로 이루어진다. 첫째 줄에는 세 정수 n, k1, k2가 공백으로 구분되어 주어진다 (0 ≤ n ≤ 100,000, 0 ≤ k1, k2 ≤ 10,000). 둘째 줄에는 길이가 k1인 비트 문자열 P1이 주어진다. k1 = 0이면 둘째 줄은 비어 있다. 셋째 줄에는 길이가 k2인 비트 문자열 P2가 주어진다. k2 = 0이면 셋째 줄은 비어 있다. 세 입력 수 n, k1, k2는 다음 조건을 만족한다. 0 < k1 ≤ n이면 n과 k1의 곱이 107을 넘지 않고, 0 < k2 ≤ n이면 n과 k2의 곱이 107을 넘지 않으며, 0 < k1 ≤ n이고 0 < k2 ≤ n이면 n, k1, k2의 곱이 107을 넘지 않는다.

출력은 표준 출력에 쓴다. 정확히 한 줄을 출력한다. 이 줄에는 길이가 n이면서 P1을 부분 문자열로 가지고 P2는 부분 문자열로 가지지 않는 비트 문자열의 개수를 1,000,000,007로 나눈 나머지 r을 출력한다 (0 ≤ r ≤ 1,000,000,006).