F - abcd

問題文

次の操作を $0$ 回以上繰り返して、 $S$ の連続部分文字列として abcd を含むようにすることができるとき、その文字列 $S$ を良い文字列ということにします。

• $S$ の先頭の文字を取り除き、取り除いた文字を $S$ の末尾に追加する

例えば、doaabc に対して操作を行ったとき、操作後の文字列は oaabcd となります。これは連続部分文字列として abcd を含むため、 doaabc は良い文字列です。

正整数 $N$ が与えられます。英小文字からなる長さ $N$ の文字列は $26^N$ 個あります。そのうち良い文字列であるものの個数を $998244353$ で割った余りを求めてください。

制約

• $4 \le N \le 2 \times 10^5$
• $N$ は整数

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル1

4

4

abcd、bcda、cdab、dabcが良い文字列です。長さ $4$ の英小文字からなる文字列であって、良い文字列は $4$ 個しかありません。

サンプル2

5

130

サンプル3

200000

951124322

$998244353$ で割った余りを出力してください。