题目描述

给定一个由 0 和 1 组成的字符串 $S$。通过对字符串 $S$ 进行以下操作 $0$ 至 $K$ 次（包括 $0$ 和 $K$）后，找出满足条件的字符串数量，并对 $998244353$ 取模。

• 选择一对整数 $i, j$，其中 $i$ 和 $j$ 是 $S$ 的索引且 $1\\leq i < j\\leq |S|$，且 $S$ 中第 $i$ 个字符是 0，第 $j$ 个字符是 1。将第 $j$ 个字符从 $S$ 中移除，并将其插入到第 $i$ 个字符的左边。

约束条件

• $1 \\leq |S| \\leq 300$
• $0 \\leq K \\leq 10^9$
• $S$ 由 0 和 1 组成。

输入

输入以标准输入给出，格式如下所示：

$S$ $K$

输出

计算满足条件的字符串数量，并对 $998244353$ 取模。

示例输入 1

0101 1

示例输出 1

4

四个字符串满足条件：0101、0110、1001 和 1010。

示例输入 2

01100110 2

示例输出 2

14

示例输入 3

1101010010101101110111100011011111011000111101110101010010101010101 20

示例输出 3

113434815