Shift

Given is a string S consisting of 0 and 1. Find the number of strings, modulo 998244353, that can result from applying the following operation on S between 0 and K times (inclusive):

• Choose a pair of integers i, j (1\leq i < j\leq |S|) such that the i-th and j-th characters of S are 0 and 1, respectively. Remove the j-th character from S and insert it to the immediate left of the i-th character.

Constraints

• 1 \leq |S| \leq 300
• 0 \leq K \leq 10^9
• S consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

S K

Output

Find the number of strings, modulo 998244353, that can result from applying the operation on S between 0 and K times (inclusive).

Examples

Input

0101 1

Output

4

Input

01100110 2

Output

14

Input

1101010010101101110111100011011111011000111101110101010010101010101 20

Output

113434815

inputFormat

Input

Input is given from Standard Input in the following format:

S K

outputFormat

Output

Find the number of strings, modulo 998244353, that can result from applying the operation on S between 0 and K times (inclusive).

Examples

Input

0101 1

Output

4

Input

01100110 2

Output

14

Input

1101010010101101110111100011011111011000111101110101010010101010101 20

Output

113434815

样例

0101 1

4