Find the number of strings of length n that lexicographically smaller or equal to S that do not contain T as substring.
### Input
- The first line contains an integer n.
- The second line contains string S.
- The third line contains string T.
### Output
- Print the number of satisfied strings, modulo 109+7.
### Constraints
- 1≤n≤1000.
- |S|=n.
- |T|≤|S|.
### Example
Input:
1cb
Output:
2