给定一个只由 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 四种字符串。