역전 개수

매년 전 세계의 수학자와 컴퓨터 과학자들이 권위 있는 역전 세기 퍼즐 대회(ICPC)에 모인다. 다음 ICPC를 위해 주최측은 다음 과제를 준비했다. 소문자로 이루어진 문자열 S가 주어졌을 때, 그 안의 역전 개수를 세어라. 역전이란 $i < j$인 인덱스 쌍 $(i, j)$ 가운데 $S_i$가 $S_j$보다 알파벳 순서에서 뒤에 오는 쌍이다.

지난달, 한 연구자 집단이 문자열의 역전 개수를 매우 빠르게 세는 알고리즘을 고안했다. 과학에는 좋은 소식이었지만, 준비해 둔 과제는 쓸모없어졌다.

문제 출제 책임자가 새로운 방안을 냈다. 참가자에게는 S 대신 S를 N번 반복한 $S^N$이 주어지고, 그 안의 역전 개수를 세어야 한다. N이 충분히 크면 연구자의 알고리즘도 너무 느려진다. 운영진은 대회를 진행했지만, 입력 파일의 정답을 더는 알지 못해 제출물을 채점할 수 없게 되었다. ICPC가 순조롭게 진행되도록 정답을 계산해 달라.

첫째 줄에 소문자로 이루어진 문자열 S가 주어진다 (1 $\le$ $|S|$ $\le$ $10^5$).

둘째 줄에 S를 반복할 횟수 N이 주어진다 (1 $\le$ N $\le$ $10^{12}$).

$S^N$의 역전 개수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.