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:
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;

int pd[310][310][310];
string s;
int k;

vector<int> cnts;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s >> k;

    int lim = 2;
    
    int cnt = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '0') {
            cnts.push_back(cnt);
            cnt = 0;
        }
        else {
            cnt++;
            lim++;
        }
    }

    cnts.push_back(cnt);
    int n = cnts.size();
    k = min(k, lim);

    pd[0][k][0] = 1;

    for (int pos = 0; pos < n; pos++) {
        for (int rem = 0; rem <= k; rem++) {
            for (int curd = 0; curd <= k; curd++) {
                for (int use = -min(cnts[pos], curd); use <= rem; use++) {
                    
                    int nrem = rem;
                    if (use > 0) nrem -= use;
                    int nuse = curd + use;

                    if (nrem < 0 || nuse < 0 || nuse >= lim) continue;

                    pd[pos+1][nrem][nuse] = (pd[pos+1][nrem][nuse] + pd[pos][rem][curd]) % mod; 
                }
            }
        }
    }

    int ans = 0;
    for (int rem = 0; rem <= k; rem++) {
        ans = (ans + pd[n][rem][0]) % mod;
    }
    
    cout << ans << endl;
}