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<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
char p[310];
int w[310], n, m, U[310], K, Mod = 998244353, CC[310];
vector<int>D[310][310][310];
int main(){
    int i, c=0, j, k, l;
    scanf("%s",p+1);
    scanf("%d",&K);
    for(i=1;p[i];i++);
    n=i-1;
    for(i=1;i<=n;i++){
        if(p[i]=='0')c++;
        else U[++m] = c, CC[c]++;
    }
    for(i=0;i<=c;i++){
        for(j=0;j<=m;j++){
            for(k=0;k<=m;k++){
                D[i][j][k].resize(CC[i]+1);
            }
        }
    }
    D[0][0][0][0]=1;
    for(i=0;i<=c;i++){
        for(j=0;j<=m;j++){
            for(k=0;k<=m;k++){
                for(l=0;l<=CC[i];l++){
                    int t = D[i][j][k][l];
                    if(!t)continue;
                    if(i!=c){
                        D[i+1][j][k][0] = (D[i+1][j][k][0]+t)%Mod;
                    }
                    if(j!=m){
                        int tp = U[j+1];
                        if(tp < i)continue;
                        if(l==CC[i]){
                            D[i][j+1][k+1][l] = (D[i][j+1][k+1][l]+t)%Mod;
                        }
                        else{
                            D[i][j+1][k][l+1] = (D[i][j+1][k][l+1]+t)%Mod;
                        }
                    }
                }
            }
        }
    }
    long long res=0;
    for(i=0;i<=K&&i<=m;i++){
        for(j=0;j<=CC[c];j++)res+=D[c][m][i][j];
    }
    printf("%lld\n",res%Mod);
}