Problem: 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

Solution (in CPP):

Solution:
// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 330, mod = 998244353;

int threshold, len, n, pre[MAX_N], dp[MAX_N][MAX_N][MAX_N], units[MAX_N];
char str[MAX_N];

int main()
{
    scanf("%s%d", str + 1, &threshold), len = strlen(str + 1);
    int last_pos = 0, ones = 0;
    for (int i = 1; i <= len; i++)
        ones += str[i] == '1';
    for (int i = 1; i <= len + 1; i++)
        if (str[i] != '1')
            units[++n] = i - last_pos - 1, last_pos = i;
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] + units[i];
    dp[0][0][0] = 1, threshold = min(threshold, ones);
    for (int i = 0; i < n; i++)
        for (int j = pre[i]; j <= pre[n]; j++)
            for (int k = 0; k <= threshold; k++)
                if (dp[i][j][k])
                {
                    for (int g = max(j, pre[i + 1]); g <= pre[n]; g++)
                        if (k + g - j - units[i + 1] <= threshold)
                        {
                            if (i + 1 == n && g - j > units[i + 1])
                                break;
                            int cost = g - j <= units[i + 1] ? 0 : g - j - units[i + 1];
                            dp[i + 1][g][k + cost] = (0LL + dp[i + 1][g][k + cost] + dp[i][j][k]) % mod;
                        }
                }
    int ans = 0;
    for (int i = 0; i <= threshold; i++)
        ans = (0LL + ans + dp[n][ones][i]) % mod;
    printf("%d\n", ans);
    return 0;
}