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>
#define ll long long
using namespace std;

ll dp[309][309][309],A[309],S[309][309][309];
ll mod = 998244353;
void admod(ll &x, ll y){
    x = (x +y) % mod;
}
int main(){
    string s;
    ll k;
    cin >> s >> k;
    ll n = s.size();
    if(k > n) k = n;
    vector<ll> A;
    ll o = 0;
    for(ll i = 0; i < n; i++){
        if(s[i] == '1') o++;
        else A.push_back(o), o =0;
    }
    A.push_back(o);
    ll m = A.size();
    reverse(A.begin(),A.end());

    dp[0][0][0] = 1;
    for(ll i = 0; i <= m; i++){
        for(ll s = 0; s <= k; s++)
            for(ll j = k; j >=0; j--)
                admod(S[i][s][j], S[i][s][j+1]);
        for(ll car = 0; car <= k; car ++){
            for(ll pl = 0; car + pl <= k; pl++){

                admod(dp[i][car][pl], S[i][car+pl][car]);
                if(i < m){
                    admod(S[i+1][car+pl][car] , dp[i][car][pl]);
                    for(ll j = 1; j <= A[i]; j++)
                        admod(dp[i+1][car + j][pl],  dp[i][car][pl]);
                }

            }
        }
    }
    ll ans = 0;
    for(ll i = 0; i <= k; i++)
        admod(ans, dp[m][0][i] );
    cout<<ans<<endl;

}