Unique Prefix String Count

For a string \(S\), let \(|S|\) denote its length. We define \(S_i\) as the \(i\)-th character of \(S\) and \(S_{L...R}\) as the substring of \(S\) from the \(L\)-th to the \(R\)-th character (inclusive), taken in order.

Given a positive integer \(n\), count the number of different strings \(S\) satisfying the following conditions:

• \(|S| = n\).
• \(S\) consists only of lowercase English letters.
• There does not exist an integer \(i \in [1, n)\) such that \(S_{1...i}\) is a subtring of \(S_{i+1...n}\). In other words, there is no way to split the string into two parts where the first part appears as a contiguous segment in the second part.

Two strings \(S\) and \(T\) are considered different if either \(|S| \neq |T|\) or there exists an index \(i \in [1, |S|]\) such that \(S_i \neq T_i\). (This is the standard definition of string equality.)

The definition of a substring: \(S\) is a substring of \(T\) if there exist indices \(L, R \in [1, |T|]\) such that \(T_{L...R} = S\).

The answer might be very large, so output the answer modulo \(998244353\).

Observation: A key observation is that for any valid string \(S\), the condition for \(i=1\) implies that the first character \(S_1\) must not appear in \(S_2...S_n\). It turns out this condition alone is sufficient to guarantee that for every valid partition \(i\) (with \(2i \le n\) when a substring of length \(i\) might appear), the substring \(S_{1...i}\) does not occur in \(S_{i+1...n}\). Therefore, the string \(S\) is valid if and only if the first character is unique in \(S\).

Thus, for \(n = 1\) the count is \(26\) (all single letters). For \(n \ge 2\), choose any letter for \(S_1\) (26 ways) and for each of the remaining \(n-1\) positions choose any letter except \(S_1\) (25 ways each). Hence, the answer is given by:

[ \text{Answer} = 26 \times 25^{n-1} \mod 998244353. ]

inputFormat

The input consists of a single integer \(n\) (\(1 \le n\)).

outputFormat

Output a single integer, the number of valid strings of length \(n\) modulo \(998244353\).

sample

1

26