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 long long MOD = 998244353;

int A[305];
int cnt[305];

char S[305];
int K, N;

long long memo[305][305][305];

long long dp(int i, int k, int skipped){
    if(skipped < 0){return 0;}
    if(k < 0){return 0;}
    if(i == 0){return skipped == 0 && k == 0;}

    if(memo[i][k][skipped] != -1){
        return memo[i][k][skipped];
    }

    long long res = 0;
    for(int j = 0; j <= 300; j ++){
        if(j >= cnt[i]){
            res += dp(i-1, k, skipped-(j-cnt[i]));
            if(skipped-(j-cnt[i]) < 0){break;}
        }else{
            res += dp(i-1, k-(cnt[i]-j), skipped+(cnt[i]-j));
        }
    }
    res %= MOD;
    //printf("dp(%d, %d, %d)=%lld\n", i, k, skipped, res);

    return memo[i][k][skipped] = res;
}

int main(){
    scanf(" %s %d", S, &K);
    N = strlen(S);
    K = min(K, N);

    memset(cnt, 0, sizeof(cnt));
    int cntZero = 0;
    int indx = 0;
    for(int i = 0; i < N; i ++){
        if(S[i] == '0'){
            cntZero ++;
        }else{
            A[indx] = cntZero+1;
            cnt[A[indx]] ++;
            indx ++;
        }
    }

    memset(memo, -1, sizeof(memo));
    long long ans = 0;
    for(int i = 0; i <= K; i ++){
        ans += dp(cntZero+1, i, 0);
    }
    ans %= MOD;
    printf("%lld", ans);

    return 0;
}