配点: 500500

問題文

0,10,1 からなる長さ NN の文字列 SS のうち、連続部分列として TT を含むものは何通りありますか。
ただし、答えは非常に大きくなる可能性があるため、 998244353998244353 で割ったあまりで求めてください。

制約

  • 1N30001 \leq N \leq 3000
  • NN は整数
  • TT0,10,1 からなる文字列
  • 1TN1 \leq |T| \leq N

入力

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

NN
TT

出力

答えを整数で出力してください。

サンプル

入力1
3
01
出力1
4

001001,010010,011011,10110144 通りです。


入力2
2
0
出力2
3

入力3
5
001
出力3
12

入力4
20
00110
出力4
438399

Submit


Go (1.21)