Inversions

Interview

Time limit0.5sMemory limit1024 MB

Summary

Given a string S and an integer N, count the inversions in S repeated N times, modulo 10^9+7.

Level: Medium4 of 10
Topics: Math, String, Combinatorics
Solved: No attempts yet

Problem

Every year, mathematicians and computer scientists from around the globe gather for the Inversion Counting Puzzle Contest (ICPC). For the next ICPC, the organizers prepared the following challenge: given a string S of lowercase letters, count the number of inversions in it. An inversion is a pair of indices i < j such that S_i comes after S_j in the alphabet.

Last month, a group of researchers devised an algorithm that counts the inversions in a string extremely fast. This was good news for science, but it made the planned challenge obsolete.

The head problem setter proposed a new idea. Instead of receiving S, participants receive S repeated N times, written $S^N$ , and must count the inversions in $S^N$ . If N is large enough, the researchers' algorithm becomes too slow. The staff went ahead with the contest, but the judges no longer know the answers to the input files, so they cannot judge submissions. Please compute the answers so the ICPC can run smoothly.

Input

The first line contains a string S (1 $\le$ $|S|$ $\le$ $10^5$ ) made of lowercase letters.

The second line contains an integer N (1 $\le$ N $\le$ $10^{12}$ ), the number of times S is repeated.

Output

Output a single line with the number of inversions in $S^N$ , modulo $10^9+7$ .

Examples4

Example 1
Input
```
ba
1
```
Expected output
```
1
```
Example 2
Input
```
ab
3
```
Expected output
```
3
```
Example 3
Input
```
zkba
1
```
Expected output
```
6
```
Example 4
Input
```
cab
7
```
Expected output
```
77
```