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;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define IN freopen("in.txt", "r", stdin);
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;

const int N = 305,MOD = 998244353;

int n,m;
int f[2][N][N];
int a[N],cnt;
char s[N];

void up(int &x,int y){
    x=x+y>=MOD?x+y-MOD:x+y;
}
int main(){
    IOS;
    cin>>(s+1)>>m;
    n=strlen(s+1),m=min(n,m);
    int l=1;
    while(l<=n){
        int r=l;
        while(r<=n && s[r]=='1')r++;
        a[++cnt]=r-l;
        l=r+1;
    }
    int now=0;
    f[now][0][0]=1;
    for(int i=cnt;i;i--){
        now^=1;
        memset(f[now],0,sizeof f[now]);
        for(int j=0;j<=m;j++)
            for(int k=0;k<=j;k++){
                if(!f[now^1][j][k])continue;
                int res=f[now^1][j][k];
                for(int t=0;t<=a[i];t++)up(f[now][j+t][k+t],res);
                for(int t=1;t<=k;t++)up(f[now][j][k-t],res);
            }
    }
    int ans=0;
    for(int i=0;i<=m;i++)up(ans,f[now][i][0]);
    cout<<ans<<endl;
    return 0;
}