#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;

#define ll long long

#ifndef ONLINE_JUDGE
#define debug(format, ...) fprintf(stderr, \
    "%s:%d: " format "\n", __func__, __LINE__,##__VA_ARGS__)
#else
#define debug(format, ...)
#define NDEBUG
#endif

// TEMPLATE STARTS BELOW

#define DEFMOD(mod, type) typedef ModInt<mod, int> type;     \
                          type operator "" _m(unsigned long long x) {   \
                              type res = x; return res; \
                          }

template<int mod, class itype> struct ModInt {
    int val;
    ModInt() {
        val = 0;
    }
    ModInt(int a) {
        val = a % mod;
    }
};

/* MODIFY AS NEEDED */

DEFMOD(998244353, mi)

template<int mod, class itype> ModInt<mod, itype> fpow(ModInt<mod, itype> base, int exponent)
{
    ModInt<mod, itype> ans = 1_m;
    ModInt<mod, itype> cur = base;
    while (exponent) {
        if (exponent & 1) ans = ans * cur;
        cur = cur * cur; exponent >>= 1;
    }
    return ans;
}

template<int mod, class itype> ModInt<mod, itype> operator+(ModInt<mod, itype> a, ModInt<mod, itype> b)
{
    ModInt<mod, itype> ans;
    ll val = (ll)(a.val) + (ll)(b.val);
    if (val >= mod) val -= mod;
    ans.val = val; return ans;
}

template<int mod, class itype> ModInt<mod, itype> operator-(ModInt<mod, itype> a, ModInt<mod, itype> b)
{
    ModInt<mod, itype> ans;
    ans.val = a.val - b.val;
    if (ans.val < 0) ans.val += mod;
    return ans;
}

template<int mod, class itype> ModInt<mod, itype> operator*(ModInt<mod, itype> a, ModInt<mod, itype> b)
{
    ModInt<mod, itype> ans;
    ans.val = ((ll)(a.val) * (ll)(b.val)) % (ll)mod;
    return ans;
}

// PRIME MOD ONLY!
template<int mod, class itype> ModInt<mod, itype> operator/(ModInt<mod, itype> a, ModInt<mod, itype> b)
{
#ifndef ONLINE_JUDGE
    if (b.val == 0) {
        fprintf(stderr, "Division by zero :(\n"); abort();
    }
#endif
    return a * fpow(b, mod - 2);
}

mi f[305][305][305];
mi hor_ps[305][305][305];
mi diag_ps[305][305][305];

char s[305];
int K, n;
int seqlen;
int seq[305];
int a[305];

int main()
{
    scanf("%s%d", s + 1, &K);
    vector<int> zeropos;
    for (int i = 1; s[i]; i++) {
        n = i;
        if (s[i] == '0') zeropos.push_back(i);
    }
    for (int i = 0; i < zeropos.size(); i++) {
        seqlen++;
        if (i == 0) {
            seq[seqlen] = zeropos[i] - 1;
        } else {
            seq[seqlen] = zeropos[i] - zeropos[i-1] - 1;
        }
        if (i == zeropos.size() - 1) {
            seqlen++; seq[seqlen] = n - zeropos[i];
        }
    }
    for (int i = 1; i <= seqlen; i++) {
        a[i] = seq[i] + a[i-1];
    }
    f[0][0][0] = 1_m;
    for (int i = 0; i <= seqlen; i++) {
        for (int j = a[i]; j <= n; j++) {
            for (int k = 0; k <= n; k++) {
                /*for (int cnt = max(a[i+1] - j, 0); j + cnt <= n; cnt++) {
                    f[i+1][j+cnt][k + max(cnt - seq[i+1], 0)]
                     = f[i+1][j+cnt][k + max(cnt - seq[i+1], 0)] + f[i][j][k];
                }*/
                if (j)
                    hor_ps[i][j][k] = hor_ps[i][j][k] + hor_ps[i][j-1][k];
                if (j && k)
                    diag_ps[i][j][k] = diag_ps[i][j][k] + diag_ps[i][j-1][k-1];

                f[i][j][k] = f[i][j][k] + hor_ps[i][j][k] + diag_ps[i][j][k];

                if (i == seqlen) continue;

                //debug("%d %d %d %d", i, j, k, f[i][j][k].val);

                int min_cnt = max(a[i+1] - j, 0);
                int max_cnt = n - j;
                if (j + min_cnt <= n) {
                    mi& hor_left = hor_ps[i+1][j+min_cnt][k];
                    hor_left = hor_left + f[i][j][k];
                }
                if (j+min(seq[i+1], max_cnt + 1) <= n) {
                    mi& hor_right = hor_ps[i+1][j+min(seq[i+1], max_cnt + 1)][k];
                    hor_right = hor_right - f[i][j][k];
                }
                if (seq[i+1] <= max_cnt) {
                    if (j + seq[i+1] <= n) {
                        mi& diag_left = diag_ps[i+1][j+seq[i+1]][k];
                        diag_left = diag_left + f[i][j][k];
                    }
                    if (j + max_cnt + 1 <= n && k + max_cnt - seq[i+1] + 1 <= n) {
                        mi& diag_right = diag_ps[i+1][j+max_cnt + 1][k + max_cnt - seq[i+1] + 1];
                        diag_right = diag_right - f[i][j][k];
                    }
                }
            }
        }
    }
    mi ans = 0;
    for (int j = 0; j <= min(K, n); j++) {
        //debug("%d %d %d %d", seqlen, a[seqlen], j, f[seqlen][a[seqlen]][j].val);
        ans = ans + f[seqlen][a[seqlen]][j];
    }
    printf("%d", ans.val);
    return 0;
}


Measured memory_bytes: 335720