配点： $500$ 点

問題文

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

制約

• $1 \leq N \leq 3000$
• $N$ は整数
• $T$ は $0,1$ からなる文字列
• $1 \leq |T| \leq N$

入力

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

出力

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

サンプル

3
01

4

$001$,$010$,$011$,$101$ の $4$ 通りです。

2
0

3

5
001

12

20
00110

438399