No tag edit access

C. Levko and Strings

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLevko 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).

Examples

Input

2 2

yz

Output

26

Input

2 3

yx

Output

2

Input

4 7

abcd

Output

21962

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/21/2018 10:58:08 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|