Password Design Problem

You need to design a password S that satisfies the following conditions:

• The length of S is N.
• S contains only lowercase English letters.
• S does not contain the substring T.
  For example: abc and abcde are substrings of abcde, but abd is not a substring of abcde.

How many different passwords satisfy the requirements?

Since the answer can be very large, output the remainder when the answer is divided by 10⁹+7.

Input Format
The first line contains an integer N, the length of the password.
The second line contains the string T, which consists only of lowercase letters.

Output Format
Output a single integer — the total number of valid passwords modulo 10⁹+7.

Data Range
1 ≤ N ≤ 50
1 ≤ |T| ≤ N, where |T| is the length of T.

Sample Input 1

2
a

Sample Output 1

625

Sample Input 2

4
cbc

Sample Output 2

456924