22985번 - 문자열 조작의 달인

문제

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

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

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

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

입력

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

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

출력

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

제한

힌트