每年，来自全球的数学家和计算机科学家都会聚集在一起，参加享誉盛名的逆序对计数谜题大赛（Inversion Counting Puzzle Contest, ICPC）。对于下一届 ICPC，组织者准备了以下挑战：给定一个由小写字母组成的字符串 $S$，计算其中逆序对的数量。一个逆序对是指一对下标 $i < j$，使得 $S_i$（位置 $i$ 处的字母）在字母表中排在 $S_j$ 之后。

然而，就在上个月，一组杰出的研究人员设计出了一种复杂的算法，可以极快地计算出字符串中的逆序对。虽然这对于科学的进步是一个好消息，但对 ICPC 的工作人员来说却是一场噩梦，因为他们计划的挑战现在已经过时了。

这个问题被反映到了总命题人那里，他随后提出了一个聪明的主意。与其仅仅给出一个字符串 $S$，不如要求参赛者在计算逆序对之前将该字符串重复 $N$ 次。如果裁判将 $N$ 设得足够大，在某种程度上，研究人员提出的算法就会开始变得太慢。ICPC 的工作人员对这个想法非常满意，于是继续组织下一届比赛。

不幸的是，现在裁判们自己也不知道输入文件的答案了，因此无法对提交的代码进行评测！ICPC 刚刚拉开帷幕，参赛者们即将开始提交他们的解决方案。请通过计算答案来帮助裁判，以便 ICPC 能够顺利进行。

输入格式

第一行包含一个由小写字母组成的字符串 $S$（$1 \le |S| \le 10^5$）。

第二行包含一个整数 $N$（$1 \le N \le 10^{12}$），表示字符串 $S$ 需要重复的次数。

输出格式

输出单行，包含一个整数，表示字符串 $S^N$（$S$ 重复 $N$ 次）中逆序对的数量。由于这个数字可能非常大，请输出它模 $10^9 + 7$ 的余数。

样例

输入样例 1

ba
1

输出样例 1

1

输入样例 2

ab
3

输出样例 2

3

输入样例 3

zkba
1

输出样例 3

6

输入样例 4

cab
7

输出样例 4

77