D. X-word Database - 水以下コンテスト

D - X-word Database

Ceylon

1024

100

点

問題文

小文字アルファベットからなる文字列 $T$ が次の2つの条件を共に満たすとき、その文字列をよい文字列と呼びます。

$T$ の長さは $X$ 以下
連続する部分列にcyanを含む

文字列 $S$ が与えられます。辞書順で $S$ 以下の文字列であり、よい文字列となるようなものは何個存在しますか？

ただし、答えが非常に大きくなることがあるので $998244353$ で割った余りを求めてください。

文字列の辞書順とは？

文字列 $A = A_1A_2\cdots A_{|A|}$ が文字列 $B = B_1B_2\cdots B_{|B|}$ より辞書順で小さいとは、以下の $2$ つのうちどちらかが成り立つ場合にいいます。ここで、 $|A|, |B|$ はそれぞれ $A, B$ の文字列の長さを表します。

$|A| < |B|$ かつ $A_1A_2\cdots A_{|A|} = B_1B_2\cdots B_{|A|}$ である。
ある整数 $1 \leq i \leq \min(|A|, |B|)$ が存在して、以下の $2$ つが成り立つ。
- $A_1A_2\cdots A_{i-1} = B_1B_2\cdots B_{i-1}$
- $A_i$ のほうが、アルファベット順で $B_i$ より前

制約

$4 \leq X \leq 10^5, X$ は整数
$1 \leq |S| \leq X$
$S$ は小文字アルファベットからなる文字列

部分点

以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられる。

(20点) $X \leq 8$
(40点) $X \leq 10^3, S$ は zのみからなる長さ $X$ の文字列
(40点) 追加の制約なし

部分点2 のみに正解し、部分点1に正解しないコードを提出した場合、得点は40点となることに注意。

入力

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

$X$
$S$

出力

答えを $998244353$ で割ったあまりを1行で出力せよ。

入力例 1

5
cyanc

出力例 1

よい文字列は、

acyan
bcyan
ccyan
cyan
cyana
cyanb
cyanc
の $7$ つです。

このサンプルは部分点1の制約を満たします。

入力例 2

8
database

出力例 2

このサンプルは部分点1の制約を満たします。

入力例 3

10
zzzzzzzzzz

出力例 3

239563112

このサンプルは部分点2の制約を満たします。

入力例 4

1599
graybrowngreencyan

出力例 4

433406175