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 MAXN = 300 + 10;
const int MOD = 998244353;

int n0, k;
string s;
int n1[MAXN];
int f[MAXN][MAXN][MAXN];

void add(int &a, int b) {
    a = (a + b) % MOD;
}

int main() {
    cin >> s >> k;
    n0 = 0;
    int cnt1 = 0;
    for(int i = 0; i < s.length(); ++i) {
        if (s[i] == '0') {
            n0++; n1[n0] = cnt1; cnt1 = 0;
        }
        else cnt1++;
    }
    n0++; n1[n0] = cnt1;
    
    for(int i = n1[1]; i <= s.length(); ++i) f[1][i - n1[1]][0] = 1;
    for(int i = 2; i <= n0; ++i) {
        for(int paid = 0; paid <= s.length(); ++paid) {
            int x = 0;
            for(int owe = paid; owe <= s.length(); ++owe) {
                add(x, f[i - 1][owe][paid]);
                add(f[i][owe][paid], x);
            }
        }
            
        for(int owe = 0; owe <= s.length(); ++owe)
            for(int paid = 0; paid <= owe; ++paid) {
                if (f[i - 1][owe][paid] == 0) continue;
                
                for(int j = 1; j <= n1[i]; ++j)
                    if (paid + j <= owe)
                        add(f[i][owe][paid + j], f[i - 1][owe][paid]);
            }
    }
    
    int res = 0;
    for(int paid = 0; paid <= min(k, (int)(s.length())); ++paid)
        add(res, f[n0][paid][paid]);
    
    cout << res << "\n";
}