시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB37346238.070%

## 문제

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 p 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