- Time limit: 1.00 s
- Memory limit: 512 MB
You are given a string of length m that is going to be padded with characters A-Z in both ends until it's length becomes n. Calculate the number of different padded strings.
Input
The first input line contains an integer n shows the length of the final string. The second line has a pattern of length m.
Output
Print the number of strings modulo 10^9+7.
Constraints
- 1 \le m \le n \le 1000
- 1 \le m \le 100
Example 1
Input:
6 ABCDB
Output:
52
Explanation: The final string will be of the form ABCDBx or xABCDB where x is any character between A–Z.
Example 2
Input:
100 YWANYWAZYWANYWA
Output:
134837038