Levko loves strings of length $*n*$, consisting of lowercase English letters, very much. He has one such string $*s*$. For each string $*t*$ of length $*n*$, Levko defines its beauty relative to $*s*$ as the number of pairs of indexes $*i*$, $*j*$ $(1 ≤ *i* ≤ *j* ≤ *n*)$, such that substring $*t*[*i*..*j*]$ is lexicographically larger than substring $*s*[*i*..*j*]$.

The boy wondered how many strings $*t*$ are there, such that their beauty relative to $*s*$ equals exactly $*k*$. Help him, find the remainder after division this number by $1000000007$ $(10^{9} + 7)$.

A substring $*s*[*i*..*j*]$ of string $*s* = *s*_{1}*s*_{2}... *s*_{*n*}$ is string $*s*_{*i*}*s*_{*i*  +  1}... *s*_{*j*}$.

String $*x*  =  *x*_{1}*x*_{2}... *x*_{*p*}$ is lexicographically larger than string $*y*  =  *y*_{1}*y*_{2}... *y*_{*p*}$, if there is such number $*r*$ ($*r* < *p*$), that $*x*_{1}  =  *y*_{1},  *x*_{2}  =  *y*_{2},  ... ,  *x*_{*r*}  =  *y*_{*r*}$ and $*x*_{*r*  +  1} > *y*_{*r*  +  1}$. The string characters are compared by their ASCII codes.

Input

The first line contains two integers $*n*$ and $*k*$ ($1 ≤ *n* ≤ 2000$, $0 ≤ *k* ≤ 2000$).

The second line contains a non-empty string $*s*$ of length $*n*$. String $*s*$ consists only of lowercase English letters.

Output

Print a single number — the answer to the problem modulo $1000000007$ $(10^{9} + 7)$.