Calculate String Transformations Length

Apply exactly t rounds of simultaneous transformation to a lowercase English string: each z is replaced with ab, and every other letter is replaced with the next letter of the alphabet. Characters produced in a round are not transformed again until the next round. Output the final string length modulo 1000000007.

输入格式

Exactly two lines: the first line is word, containing only a..z; the second line is a non-negative integer t. Based on the original Java int interface and the round semantics, this site explicitly interprets 0≤t≤2147483647; this range is derived from the type rather than given as a number in the original constraints section. The original has no upper bound on the length of word; this site covers every valid transmittable string within the 32MiB standard input budget of a single test case, without further reducing the length. The first line may be empty, as this site's mathematical extension to the empty string.

输出格式

Output one integer: the final length modulo 1000000007. When t=0, return the original length modulo it; an empty string always returns 0.

样例 1

输入：

azbk
1

输出：

5

样例 2

输入：

abczy
2

输出：

7

样例 3

输入：

z
0

输出：

1

样例说明

In the original statement, azbk becomes babcl after one round, length 5. In the original example abczy,t=2, it first becomes bcdabz and then cdebcab, length 7; the original output was TO-DO, and 7 was filled in by this site by deriving it from the explicit rules; the original explanation cdedbc is wrong. The third public example z,t=0→1 is a boundary case added by this site.