30484번 - Inversions 다국어

문제

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

However, just last month, a group of outstanding researchers devised a sophisticated algorithm that can count the inversions in a string extremely fast. While this was great news for the advancement of science, it has been a nightmare for the ICPC staff, since their planned challenge is now obsolete.

This issue escalated to the head problem setter, who then presented a clever idea. Instead of simply receiving a string S, they should ask participants to repeat this string N times before counting the inversions. If the judges then set N to be large enough, at some point the algorithm proposed by the researchers will start to be too slow. Happy with this idea, the ICPC staff went ahead with organizing the next contest.

Unfortunately, now the judges don’t know the answers to the input files anymore, and therefore can’t judge submissions! The ICPC has just kicked off, and participants are about to start submitting their solutions. Please help the judges by computing the answers, so that the ICPC can run smoothly.

입력

The first line contains a string S (1 ≤ |S| ≤ 10⁵), which is made of lowercase letters.

The second line contains an integer N (1 ≤ N ≤ 10¹²) indicating how many times the string S is to be repeated.

출력

Output a single line with an integer indicating the number of inversions in the string S^N (S repeated N times). Because this number can be very large, output the remainder of dividing it by 10⁹ + 7.

제한

힌트