Problem Description

Kuzuryu received a palindrome \( S \) of length \( N \) consisting only of lowercase English letters from a girl.

However, Kuzuryu's disciple Aichan played a prank on this palindrome by performing the following actions:

• Exactly \( K \) times, change the \( i \)-th character of \( S \) (where \( 1 \leq i \leq N \)) to a different lowercase English letter (note that the same position can be chosen multiple times).

Given the string \( T \) after the prank and the integer \( K \), find the number of possible original palindromes modulo \( 10^9 + 7 \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( K \) \( T \)

Output Format

Output the number of possible original palindromes modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

5 1
abbaa

Sample Output #1

2

Sample Input #2

4 1
aaaa

Sample Output #2

0

Sample Input #3

1 100
a

Sample Output #3

26

Sample Input #4

11 7
abracadabra

Sample Output #4

1019576

Notes/Hints

Constraints

• \( N \) is an integer satisfying \( 1 \leq N \leq 2 \times 10^5 \)
• \( K \) is an integer satisfying \( 0 \leq K \leq 10^9 \)
• \( |T| = N \)
• \( T \) consists only of lowercase English letters

Sample Explanation 1

• aabaa, abbba satisfy the conditions.

Sample Explanation 2

• Note that the operation must be performed exactly \( K \) times.

见题面 Input 部分

见题面 Output 部分