問題文

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$ で割った余りを出力せよ。

入力例 1

0101 1

出力例 1

4

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

入力例 2

01100110 2

出力例 2

14

入力例 3

1101010010101101110111100011011111011000111101110101010010101010101 20

出力例 3

113434815