Description

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

Input Format

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

Output Format

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

2

650

105383595

114514

Hint

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