시간 제한메모리 제한제출정답맞은 사람정답 비율
2.5 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)87403859.375%

문제

소문자 알파벳으로 이루어진 길이 $N$의 문자열 $S$가 있다. 문자열을 자유자재로 다루는 달인 Taro는 여기에 다음과 같은 조작을 $M$번 가하려고 한다.

  • 위치 $1 \leq i \leq N$을 하나 골라서, $S_i$를 알파벳 순서로 다음에 오는 문자로 바꾼다.
    • 단, 고른 문자가 z라면 조작을 가하더라도 z가 된다.

예를 들어 az라는 문자열이 존재한다고 했을 때, $i=1$을 고르면 bz로 바뀌지만 $i=2$를 고르면 문자열이 바뀌지 않는다.

이렇게 조작을 $M$번 가했을 때 나올 수 있는 문자열의 개수를 구하자. 

입력

다음과 같이 입력이 주어진다.

$N\ M$
$S$
  • $1 \leq N \leq 300$, $0 \leq M \leq 10^{18}$
  • 입력으로 주어지는 문자열 $S$는 알파벳 소문자만으로 이루어져 있다.

출력

주어진 문자열에 조작을 $M$번 가했을 때 나올 수 있는 문자열의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.

예제 입력 1

2 2
az

예제 출력 1

3

나올 수 있는 문자열은 az, bz, cz의 $3$개이다.

예제 입력 2

2 2
ay

예제 출력 2

3

나올 수 있는 문자열은 cy, bz, az의 $3$개이다.