Una inversión de un texto es un par de posiciones \(i < j\) tal que la letra en \(i\) va después que la letra en \(j\) en el alfabeto. Dado un texto \(S\) y un entero \(N\), cuenta las inversiones del texto \(S^N\) (\(S\) repetido \(N\) veces seguidas).

Entrada

La primera línea tiene el texto \(S\) \((1 \le |S| \le 10^5)\), de letras minúsculas.

La segunda línea tiene un entero \(N\) \((1 \le N \le 10^{12})\).

Salida

Una línea con la cantidad de inversiones de \(S^N\), módulo \(10^9 + 7\).

Ejemplo 1

Entrada

ba
1

Salida

1

Ejemplo 2

Entrada

ab
3

Salida

3

Ejemplo 3

Entrada

zkba
1

Salida

6

Ejemplo 4

Entrada

cab
7

Salida

77

Regional Latinoamericana 2023 del ICPC, problema I («Inversions»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.