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

const int mod = 998244353;
const int N = 305;

int dp[N][N][N];
vector<int> ones;
int one_cnt;
int K;

int solve(int var, int op, int pref) {
    if(op > K or op < 0) return 0;
    if(var == ones.size()) return pref == one_cnt;
    if(dp[var][op][pref] != -1) return dp[var][op][pref];
    int ans = 0;
    int kone = ones[var] - (var > 0 ? ones[var-1] : 0);
    for(int x = max(0, ones[var]-pref); x + pref <= one_cnt; x++) {
        int new_op = op+max(0, x-kone);
        ans += solve(var + 1, new_op , x+pref);
        if(ans >= mod) ans -= mod;
    }
    return dp[var][op][pref] = ans;
}


int main() {
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s >> K;
    s.insert(s.begin(), '0');
    s.push_back('0');
    vector<int> zeros;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '0') zeros.push_back(i);
    }
    for(int i = 1; i < zeros.size(); i++) {
        int l = zeros[i-1]+1, r = zeros[i]-1;
        ones.push_back(max(0,r-l+1));
    }
//    for(int x : ones) {
//        cout << x << " ";
//    }
//    cout << endl;
    for(int x : ones) one_cnt += x;
    for(int i = 1; i < ones.size(); i++) {
        ones[i] += ones[i-1];
    }
    memset(dp, -1, sizeof dp);
    cout << solve(0, 0, 0) << endl;
    return 0;
}