P5337 [TJOI2019] Mr. Toluene's String

TJOI2019 D1T1. Source file name: str.*. Time limit: 1 s. Memory limit: 128 M.

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

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 one integer, representing the total number of strings that Xiao Toluene can write. Take the result modulo $10^9+7$.

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