Problem Background

Eztsu is a lovely girl who has recently learned about Suffix Trees and plans to use them to solve the following problem.

Problem 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 the characters from the \( L \)-th to the \( R \)-th character of \( S \) from left to right.

Given \( n \), find how many different strings \( S \) satisfy the following requirements:

• \( |S| = n \).
• \( S \) contains only lowercase letters.
• There is no integer \( i \in [1, n) \) such that \( S_{1...i} \) is a substring of \( S_{i+1...n} \).

In simpler terms, 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 considered different if and only if \( |S| \neq |T| \) or there exists an \( i \in [1, |S|] \) where \( S_i \neq T_i \). If you are unsure what this means, you can understand it as them looking different.

Poor Eztsu can't solve this, so you need to help her with this problem.

The answer may be very large, so you only need to output the answer modulo \( 998244353 \).

Additional Clarification:

\( 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

A single line containing a positive integer \( n \), as described in the problem.

Output Format

A single line containing an integer, the answer modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

2

Sample Output #1

650

Sample Input #2

105383595

Sample Output #2

114514

Notes

Sample Explanation

For the first sample, it is easy to see that the string meets the criteria if and only if the two characters are different. Therefore, the answer is \( 26 \times 26 - 26 \), which can be understood as the total number of ways to choose two characters minus the number of ways where both characters are the same.

Data Range

"This problem uses bundled testing."

For all test cases, it is guaranteed that \( 1 \leq n \leq 10^9 \).

Subtask 1 (17 pts) \( n \leq 4 \).

Subtask 2 (78 pts) \( n \leq 2 \times 10^3 \).

Subtask 3 (5 pts) No special restrictions.

Hints

There are 26 lowercase letters.

见题面 Input 部分

见题面 Output 部分