P16339 「WAOI Round 4.5」Dead Loop

Define $\operatorname{repeat}(s, x)$ as the string obtained by repeating the string $s$ exactly $x$ times. For example: $$ \operatorname{repeat}(\texttt{AAAB}, 3) = \texttt{AAABAAABAAAB} $$ Define the numeric value of a lowercase string $s$ as follows: Replace each character $c$ in $s$ with the difference between the ASCII code of $c$ and the ASCII code of the lowercase letter `a`, then interpret the resulting sequence as a base-$26$ number. For example, the numeric value of $\texttt{bc}$ is: $$ 1 \times 26 + 2 = 28 $$ Now define a repeat transformation on a lowercase string $s$: After applying the repeat transformation to $s$, the string becomes $$ \operatorname{repeat}(s, \text{numeric value of } s) $$ Now, wwwwwza has a lowercase string $s$. He wants to know the value of the numeric value of $s$ after applying the repeat transformation exactly $k$ times, modulo $2^p$.

The first line contains two positive integers, $k$ and $p$. The second line contains a lowercase string $s$.

Output a single integer, representing the answer.

**Explanation of Sample 1** The numeric value of `c` is $2$, so after one repeat transformation, $s$ becomes `cc`. The numeric value of `cc` is: $2 \times 26 + 2 = 54$. **Explanation of Sample 2** From Sample 1, after one repeat transformation, $s$ becomes `cc`, whose numeric value is $54$. So after the second repeat transformation, $s$ becomes `ccc...c` with a total of $108$ occurrences of `c`. Therefore, the numeric value of $s$ is $\sum_{i=0}^{107} 2 \times 26^i \equiv 1966 \pmod{2^{13}}$. **Constraints** Let $\operatorname{len}$ denote the length of $s$. For $100\%$ of the data: * $1 \le \operatorname{len} \le 10^6$; * $1 \le k \le 10^{18}$; * $1 \le p \le 20$; * $s$ consists only of lowercase English letters. | Subtask | Score | $\operatorname{len} \le$ | $k \le$ | | :-----: | :----: | :------------------------: | :---------: | | $1$ | $30$ | $10$ | $2$ | | $2$ | $20$ | $1000$ | $1000$ | | $3$ | $50$ | $10^6$ | $10^{18}$ |