单词 strawberry 中有多少个 r？这很简单，显然答案是 3。但对于大语言模型（LLM）来说，答案并没有那么显而易见，早期的模型会认为该单词中只有 2 个。

为了进一步戏弄 LLM，你决定将一个字符串 $s$ 重复 $N$ 次。每次重复时，你都会将每个字母替换为字母表中它的前一个字母，其中 a 变成 z。例如，单词 abacus 变成 zazbtr。

如果我们将单词 strawberry 总共重复 3 次，我们会得到字符串 strawberryrsqzvadqqxqrpyuzcppw。这个字符串中包含 5 个字母 r。

给定一个单词和它被重复的总次数，计算 r 在最终字符串中出现的次数！

输入格式

输入的第一行包含一个由小写字母组成的字符串 $s$（$1 \le |s| \le 1000$）。

第二行包含一个整数 $N$（$1 \le N \le 10^{15}$），表示 $s$ 被重复的总次数（包括初始字符串），其中每次重复时每个字母都会被替换为其前一个字母。

输出格式

输出 r 在最终字符串中出现的次数。

样例

输入样例 1

strawberry
3

输出样例 1

5

输入样例 2

abacus
5

输出样例 2

2

输入样例 3

r
26

输出样例 3

1

输入样例 4

r
27

输出样例 4

2

输入样例 5

r
26000000000

输出样例 5

1000000000