Background

TJOI2019 D1T1.

Source file name: str.*.

Time limit: 1 s. Memory limit: 128 M.

Problem Description

One day, Xiao Toluene received a divine message. He wants to write it down, but cannot reveal the secret, so he decides to record it in a special way.

The divine message is a string, denoted as $s_1$. $s_1$ contains only $26$ lowercase letters. Now Xiao Toluene wants to write down the message as another string, denoted as $s_2$. $s_2$ also contains only $26$ lowercase letters. The requirement is: any two adjacent letters in $s_1$ must not appear adjacent in $s_2$.

Given the length of $s_2$, Xiao Toluene wants to know how many different strings $s_2$ he can write. Output the number of valid strings modulo $10^9+7$.

Input Format

The first line contains a single positive integer $n$, representing the length of string $s_2$.

The second line contains a string, representing string $s_1$.

Output Format

Output one integer, representing the total number of strings that Xiao Toluene can write. Take the result modulo $10^9+7$.

2
ab

675

Hint

For $30\%$ of the testdata, $n \le 100000$.

For $100\%$ of the testdata, $1 \le n \le 10^{15}$, $|s_1| \le 10^5$.

Note: The adjacency restriction requires the same order. For example, in the sample, $s_2$ must not contain $\text{ab}$, and only $\text{ab}$ is forbidden, but $\text{ba}$ is allowed.

Translated by ChatGPT 5