配点： 点
問題文
からなる長さ の文字列 のうち、連続部分列として を含むものは何通りありますか。
ただし、答えは非常に大きくなる可能性があるため、 で割ったあまりで求めてください。
制約
- は整数
- は からなる文字列
入力
入力は以下の形式で標準入力から与えられます。
出力
答えを整数で出力してください。
サンプル
入力1
3 01
出力1
4
,,, の 通りです。
入力2
2 0
出力2
3
入力3
5 001
出力3
12
入力4
20 00110
出力4
438399
提出
登録なしで提出できます。
Go (1.14)