题解

题面描述

小红在设置密码的时候，系统提示她密码太简单了，因此她决定使用一种自定义的加密算法来设置更为复杂的密码。
她的方法是：每次发现密码中有大写字母时，就将这个大写字母重复写一次。
例如，对于初始密码字符串
$s = "aBcbA"$ 经过一次加密操作后，密码将变为
$"aBBcbAA"$

题目内容

小红在设置密码的时候，系统提示她密码太简单了，因此她决定使用一种自定义的加密算法来设置更为复杂的密码。

她的方法是：每次发现密码中有大写字母时，就将这个大写字母重复写一次。例如，对于初始密码字符串 "$aBcbA$" 经过一次加密操作后，密码将变为"$aBBcbAA$"。

现在，小红对给定的密码字符串进行了$k$ 次加密操作，请你计算最终密码字符串的长度。

输入描述

第一行输入一个长度不超过 $10^6$ 、且由大小写字母混合构成的的字符串 $s$ 代表初始密码。

第二行输入一个整数 $k(0 ≦ k ≦ 10^9)$ 代表加密次数。

输出描述

在一行上输出一个整数，代表加密后密码的长度。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

样例1

输入

Ciallo
2

输出

9

说明

第一次加密后得到"$CCiallo$"；第二次加密后得到"$CCCCiallo$"