One day, Mr. Toluene received a divine instruction and needed to write it down. However, he could not reveal the secrets of heaven, so he had to use a specific method to record the instruction. The divine instruction is a string, denoted as $s_1$, which only contains lowercase letters $a-z$. Now, Mr. Toluene wants to write down the instruction as a string $s_2$, which also only contains lowercase letters $a-z$. The requirement is that no two adjacent letters in $s_1$ can appear adjacently in $s_2$ in the same order. Given the length of $s_2$, Mr. Toluene wants to know how many ways he can write down the divine instruction. Output the number of ways modulo $10^9 + 7$.

Input

The first line contains a single positive integer $n$, representing the length of the string $s_2$, where $n \le 10^{15}$. The second line contains a string, representing the string $s_1$. The length of $s_1$ does not exceed $100000$.

Output

Output a single integer representing the total number of strings Mr. Toluene can write. The result should be modulo $10^9 + 7$.

Examples

Input 1

2
ab

Output 1

675

Constraints

For $30\%$ of the data, $n \le 100000$. For $100\%$ of the data, $n \le 10^{15}$.