시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 1024 MB 127 32 16 19.512%

문제

A finite sequence of 0 and 1 is called a bit string. The length of a bit string w is the number of symbols contained in w. Note that the empty string is also a bit string of length zero. A substring of a bit string w is a consecutive portion of w. Note that the empty string is a substring of any bit string and any bit string is a substring of itself. For example, consider a bit string 1010 of length four. All substrings of 1010 are listed as follows: 1010, 101, 010, 10, 01, 1, 0, and the empty string. Bit strings 100 and 11 are not substrings of 1010. If a bit string P is a substring of a bit string w, then we say that w contains w as a substring or w contains P, shortly.

Consider all bit strings of length n. It is easy to see that there are exactly 2n bit strings of length n in total. Given a nonnegative integer n and two bit strings P1 and P2, write a program that outputs the number of bit strings of length n that contain P1 but do not contain P2.

입력

Your program is to read from standard input. The input consists of three lines. The first line consists of three integers, n, k1, and k2 (0 ≤ n ≤ 100,000, 0 ≤ k1, k2 ≤ 10,000), separated by a space. The second line consists of a single bit string, representing P1 whose length is k1. If k1 = 0, then the second line is empty. The third line consists of a single bit string, representing P2 whose length is k2. If k2 = 0, then the third line is empty. The three input numbers n, k1, and k2 satisfy the following conditions: If 0 < k1n, then the product of n and k1 does not exceed 107; if 0 < k2n, then the product of n and k2 does not exceed 107; if 0 < k1n and 0 < k2n, then the product of n, k1, and k2 does not exceed 107.

출력

Your program is to write to standard output. Print exactly one line. The line should contain an integer r, where 0 ≤ r ≤ 1,000,000,006 is the remainder when dividing by 1,000,000,007 the number of bit strings of length n that contain P1 but do not contain P2.

예제 입력 1

4 2 2
10
11

예제 출력 1

6

예제 입력 2

4 2 3
10
100

예제 출력 2

7