配点 : $800$ 点

問題文

0 と 1 のみからなる文字列 $S$ が与えられます。$S$ に以下の操作を $0$ 回以上 $K$ 回以下繰り返してできる可能性のある文字列の個数を $998244353$ で割った余りを求めてください。

• 整数 $1\leq i < j\leq |S|$ の組であって、$S$ の $i$ 文字目が 0 であり $j$ 文字目が 1 であるものを選ぶ。$S$ の $j$ 文字目を取り除き、$i$ 文字目の直前の位置に挿入する。

制約

• $1 \leq |S| \leq 300$
• $0 \leq K \leq 10^9$
• $S$ は 0, 1 のみからなる

入力

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

$S$ $K$

出力

$S$ に操作を $0$ 回以上 $K$ 回以下繰り返してできる可能性のある文字列の個数を $998244353$ で割った余りを出力せよ。

0101 1

4

0101, 0110, 1001, 1010 の $4$ 通りの文字列ができる可能性があります。

01100110 2

14

1101010010101101110111100011011111011000111101110101010010101010101 20

113434815