## DP Finite Automata with Compression: Password Counting

You now need to design a password S,S Need to meet:

S The length is N； S Only contain lowercase English letters; S Does not contain substring T； E.g: abc and abcde are abcde’s substring while abde is not a substring of abcde.

How many different passwords meet the requirements?

Since the answer will be very large, please output the answer modulus 109 + 7 The remainder.

Input format

Enter the integer N in the first line to indicate the length of the password.

Enter the string T on the second line. T contains only lowercase letters.

Output format

Output a positive integer , which means the total password number modulus109+ 7 After the result.

data range

Sample Input:

4
cbc


Sample Output:

456924


### Solution

Use T to generate a KMP state transition table. Looping from 0 to N and test every possible charater (a-z), the KMP state transition from j to newJ based on charater in position i+1. Add the numbers to that state.

dp[i][j]: the number of passwords so far from 0 to i-th Position

• i is the i-th position of the password(< N)
• j is the j-th state of KMP state.