002 - FizzBuzz Subsequence Problem 2

時間制限 0.5 秒 / メモリ制限 32 MB / 得点 3 / x 4 /


TLE
0.5sec
MLE
32MB
得点
3

問題

文字列$S$がある。
文字列には価値がある。
$S$に対して、$S$を構成する文字を0文字以上取り除き、残った文字を元の順序で並べることで得られる文字列を$S$の部分文字列と呼ぶ。
この時、同じ文字列であっても$S$に対する文字の位置が違えば別の部分文字列とする。
FizzBuzz的視点から文字列を評価すると、部分文字列に"Fizz"や"Buzz"がいくつ存在するかが重要になる。
文字列の価値は、$S$から抽出できる部分文字列のうち"Fizz"があれば+3、"Buzz"があれば+5される。
つまり、『"Fizz"の個数 * 3 + "Buzz"の個数 * 5』が$S$の価値となる。

例えば、"FizzBuzz"は"Fizz"が6つ、"Buzz"が1つあるので6*3+1*5 = 23が価値になる。

文字列$S$が与えられるので$S$の価値を答えよ。
ただし、価値は非常に大きくなる場合があるので、998'244'353で割ったあまりを出力せよ。

制約

  • 1 ≤ |$S$| ≤ 105
  • $S$には大小英字、数字、アンダーバー(_)が含まれる

入出力例

例1

入力
FizzBuzz
出力
23

例2

入力
fizzbuzz
出力
0
"fizz","FIZZ,"fIZZ"いずれも"Fizz"ではない。"Buzz"も同様。文字の大小は区別される。

例3

入力
Xx_zzuBBuzz_xX
出力
10

例4

入力
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
出力
629915647
本来の価値は1628160000であるが、998244353で割ったあまりを出力することに注意せよ。