問題文

「ヌメロニム」とは、$2$ 文字以上の文字列を、数字を用いて省略した文字列で、元の文字列の先頭と末尾のみ残し、間にあった文字をその文字数で置き換えたものです。

例えば、"internationalization" という文字列は、"i" + ($18$ 文字) + "n" で構成されているので、ヌメロニムにすると "i18n" となります。
単語全体の長さではなく、先頭と末尾を除いた長さを用いることに注意してください。
他にも、"animal" は "a4l"、"cat" は "c1t"、"we" は "w0e"と変換されます。
$1$ 文字以下の文字列（$1$ 文字からなる文字列と、空文字列）にはヌメロニムは定義されません。

"i" と "n" のみからなる長さ $N$ の文字列 $S$ が与えられます。
$S$ の連続とは限らない部分列のとり方は、 $2^N$ 通りあります。
このうち、部分列の長さが $2$ 以上であって、ヌメロニムが "i$k$n" になる部分列のとり方の個数を $998244353$ で割った余りを、$X_k$ とします。
すべての $k = 0,1,2, ..., N-2$ についての $X_k$ の排他的論理和(xor) $X_0 \oplus X_1 \oplus \cdots \oplus X_{N-2}$ を求めてください。
ただし、二つの部分列のとり方が異なるとは、ある $i(1\leq i\leq N)$ が存在して、文字列 $S$ の $i$ 文字目が、一方の部分列では使われているが、もう一方の部分列では使われていないことを指します。
文字列として同じ部分列であっても、とり方が違うものは個別に数えることに注意してください。

入力

$N$
$S$

$2 \leq N \leq 300000$
$N$ は整数
$S$ は "i" と "n" のみからなる文字列である。

出力

答えを $1$ 行で出力してください。
最後に改行してください。

サンプル

3
inn

3

6
ininin

3

8
nnnnniii

0

40
ininnninniiinnnninininininnnniininninnin

74145471