Let's define the weight of an English letter (lowercase or uppercase) in the following way: a has weight 1, b = 2, and so on until z = 26; A = 27 and so on until Z = 52. The weight of an alphabetic string is the sum of weights of all letters it contains, modulo M.

Next, let's define the sum of two strings X and Y of length N consisting of lowercase English letters as a string Z of length N such that for each valid i, the weight of the i-th character of Z is the sum of weights of the i-th characters of X and Y. For example, the sum of strings "abzaa" and "abcde" is the string "bdCef".

enter image description here

You are given a string S of lowercase English letters with length N and two integers M and K. You need to select a string B (also consisting only of lowercase English letters) such that the sum of strings S and B has weight K.

Can you find the number of ways to select the string B modulo \( 10^9+7 \)?

Constraints

\( 1 \le N \le 200,000 \)
\( 100,000 \le M \le 1,000,000,007 \)
\( 0 \le K < M \)
the string S will consist only of lowercase English letters

Input format

The first line of the input contains three space-separated integers N, M and K.

The second line contains a single string S of length N.

Output format

Print a single line containing one integer — the answer modulo \( 10^9+7 \).