No.3584 Camouflage Mole
marc2825
siganaiProblem Statement
The string camouflage contains
mole hidden as a (not necessarily contiguous) subsequence.
For a string \(S\) of length \(N\) consisting of the 26 lowercase English letters a-z, define \(f(S)\) as
"the number of (not necessarily contiguous) subsequences of \(S\) that are equal to the string mole"†.
There are \(26^N\) lowercase English strings of length \(N\) in total. Find the sum of \(f(S)\) over all these strings \(S\), modulo \(998244353\).
† More precisely, \(f(S)\) is the number of $4$-tuples \((i,j,k,l)\) satisfying \(1 \le i < j < k < l \le N\) and \(S_i=\mathrm{m},\ S_j=\mathrm{o},\ S_k=\mathrm{l},\ S_l=\mathrm{e}\).
Constraints
- \(4 \le N \le 2 \times 10^5\)
- All inputs are integers.
Input
The input is given from standard input in the following format.
$N$
Output
Print the answer modulo \(998244353\) on a single line.
Sample
Sample 1
Input
4
Output
1
The only string of length 4 that contains mole as a subsequence is the string
mole itself.
Sample 2
Input
6
Output
10140
Sample 3
Input
100
Output
774511835
Since the answer can be very large, print it modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。