Problem Description

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$.

Input Format

The first line contains two positive integers, $k$ and $p$.

The second line contains a lowercase string $s$.

Output Format

Output a single integer, representing the answer.

1 11
c

54

2 13
c

1966

Hint

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$
$3$	$50$	$10^6$	$10^{18}$