题目描述

给定一个只由 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

输入

0101 1

输出

4

样例 2

输入

01100110 2

输出

14

样例 3

输入

1101010010101101110111100011011111011000111101110101010010101010101 20

输出

113434815

说明/提示

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

样例解释 1

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