#include <bits/stdc++.h>

using namespace std;


#ifdef zxc

#include <sys/resource.h>
#include "debug.h"
#include "profile.h"

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define profile(X) LOG_DURATION(X)
#else
#define debug(...) 42
#define profile(...) 42
#endif

using ll = int64_t;
using ld = double;
const ld EPS = 1e-9;
const ll MOD = 998244353;
const ld PI = 3.141592653589793;
const int maxn = 600001;
using cd = complex<double>;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

ll fac[maxn];
ll inv[maxn];

ll pw(ll a, ll b) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
    }
    return res;
}

void prep(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    inv[n] = pw(fac[n], MOD - 2);
    for (int i = n - 1; i >= 0; --i) {
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    }
}

ll C(int n, int k) {
    if (k > n || k < 0) {
        return 0;
    }
    return fac[n] * inv[k] % MOD * inv[n - k] % MOD;
}

int dp[2][301][301];
int pref[2][301][301];

signed main() {
#ifdef zxc
    struct rlimit rl;
    const rlim_t kStackSize = 512L * 1024L * 1024L;
    assert(!getrlimit(RLIMIT_STACK, &rl));
    rl.rlim_cur = kStackSize;
    assert(!setrlimit(RLIMIT_STACK, &rl));
    freopen("../input.txt", "r", stdin);
//    freopen("../kolya_output.txt", "w", stdout);
#else
    //    mt19937 mt(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    //            freopen("", "r", stdin);
    //        freopen("hack.out", "w", stdout);
#endif
    profile("all");
    mt19937 mt(234793824);
    auto solve = [&mt](int _) {
        string s;
        cin >> s;
        int k;
        cin >> k;
        if (s.find('0') == s.npos) {
            cout << 1;
            return;
        }
        vector<int> sz;
        int i = -1;
        while (i < int(s.size())) {
            auto x = s.find('0', i + 1);
            if (x == s.npos) {
                x = s.size();
            }
            sz.push_back(x - i - 1);
            i = x;
        }
        auto add = [](int a, int b) {
            a += b;
            if (a >= MOD) {
                a -= MOD;
            }
            return a;
        };
        reverse(sz.begin(), sz.end());
        debug(sz);
        k = min<int>(k, count(s.begin(), s.end(), '1'));
        pref[0][k][0] = 1;
        pref[0][k][1] = -1;
        for (int bucket = 0; bucket < sz.size(); ++bucket) {
            int cur = bucket & 1;
            int nxt = cur ^1;
            for (int K = 0; K <= k; ++K) {
                fill(pref[nxt][K], pref[nxt][K] + 301, 0);
            }
            for (int K = 0; K <= k; ++K) {
                int acc = 0;
                for (int i = 0; i <= k; ++i) {
                    acc = add(acc, pref[cur][K][i]);
                    dp[cur][K][i] = acc;
                }

                for (int free = 0; free <= k; ++free) {
                    auto cur_dp = dp[cur][K][free];
                    debug(bucket, K, free, dp[cur][K][free]);
                    for (int x = 0; x <= K && x <= sz[bucket]; ++x) {
                        pref[nxt][K - x][free + x] = add(pref[nxt][K - x][free + x], cur_dp);
                        pref[nxt][K - x][free + x + 1] = add(pref[nxt][K - x][free + x + 1], MOD - cur_dp);
                    }
                    int mx = free - 1;
                    pref[nxt][K][0] = add(pref[nxt][K][0], cur_dp);
                    pref[nxt][K][mx + 1] = add(pref[nxt][K][mx + 1], MOD - cur_dp);
                }
            }
        }
        int ans = 0;
        for (int K = 0; K <= k; ++K) {
            ans = add(ans, pref[sz.size() & 1][K][0]);
        }
        cout << ans;
    };


    fast_io();

    cout.precision(9);
    cout <<
         fixed;
    for (int i = 1; i <= 1; ++i)
        solve(1);


}


Measured memory_bytes: 5004