P6045 Suffix Tree

Eztsu is a cute girl. Recently, she learned about the [suffix tree](https://www.luogu.com.cn/blog/EternalAlexander/xuan-ku-hou-zhui-shu-mo-shu), and plans to use it to solve the following problem.

For a string $S$, we define $|S|$ as the length of $S$. Next, we define $S_i$ as the $i$-th character of $S$, and $S_{L...R}$ as the string formed by concatenating, from left to right, the $L$-th character to the $R$-th character of $S$. Given $n$, find how many different strings $S$ satisfy all of the following: - $|S|=n$. - $S$ contains only lowercase letters. - There does not exist an integer $i \in [1,n)$ such that $S_{1...i}$ is a substring of $S_{i+1...n}$. For the third constraint, in simpler words: there is no way to split the string into two parts such that the first part is a substring of the second part. Two strings $S$ and $T$ are different if and only if $|S|\neq|T|$ or $\exists i \in [1,|S|] \ S_i \neq T_i$. If you do not know what this means, you can just think that they look different. Poor Eztsu cannot solve it, so you need to help her. The answer may be very large. You only need to output the value of the answer modulo $998244353$. Additional note: $S$ is a substring of $T$ if and only if there exist $L,R \in [1,|T|]$ such that $T_{L...R}=S$.

One line containing a positive integer $n$, as described in the statement.

One line containing an integer: the answer modulo $998244353$.

#### Sample Explanation For the first sample, it is not hard to see that the string satisfies the requirements if and only if the two characters are different. Therefore, the answer is $26 \times 26 - 26$, which can be understood as the number of ways to choose any two characters minus the number of ways where the two characters are the same. --- #### Constraints **This problem uses bundled testdata.** For all test points, $1 \leq n \leq 10^9$ is guaranteed. $\text{Subtask 1 (17 pts)}$ $n \leq 4$. $\text{Subtask 2 (78 pts)}$ $n \leq 2\times 10^3$. $\text{Subtask 3 (5 pts)}$ No special constraints. --- #### Hint There are $26$ lowercase letters in total. Translated by ChatGPT 5