题目描述

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

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

输入格式

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

$S$ $K$

输出格式

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

题目大意

给定一个只由 0 和 1 组成的序列 $S$ 。求对 $S$ 进行以下的操作 $[0,k]$ 次后可以得到的字符串种类个数模 $998244353$ 后的值。

• 选取一对整数 $i,j \space (1 \le i < j \le |S|)$ ，使得 $S_i$ 为 0 且 $S_j$ 为 1。将 $S_j$ 删去，并将这个数插在 $S_i$ 之前。

输入格式

一行，为字符串 $S$ 和常数 $k$。

输出格式

一行一个整数，代表对 $S$ 进行操作 $[0,k]$ 次后可以得到的字符串种类个数模 $998244353$ 后的值。

数据范围与约定

• $1 \le |S| \le 300$
• $0 \le k \le 10^9$
• $S$ 只包含 0 和 1

样例解释 1

可能形成 0101, 0110, 1001, 1010 四种字符串。

0101 1

4

01100110 2

14

1101010010101101110111100011011111011000111101110101010010101010101 20

113434815

提示

制約

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

Sample Explanation 1

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