#include "bits/stdc++.h"
using namespace std;
typedef long long li;

template <long long mod>
struct modint {
    long long x;

    modint<mod>(): x(0LL) {}
    modint<mod>(const long long _data) {
        if (_data < 0) {
            x = (_data % mod + mod) % mod;
        } else if (_data >= mod) {
            x = _data % mod;
        } else {
            x = _data;
        }
    }

    bool operator==(const modint<mod>& op) const {
        return x == op.x;
    }

    bool operator!=(const modint<mod>& op) const {
        return !((*this) == op);
    }

    modint<mod> operator-() const {
        if (x == 0) {
            return modint(0);
        }
        return modint(mod - x);
    }

    modint<mod> operator+(const modint<mod>& op) const {
        const long long newdata = x + op.x;
        if (newdata >= mod) {
            return modint<mod>(newdata - mod);
        } else {
            return modint<mod>(newdata);
        }
    }

    modint<mod>& operator+=(const modint<mod>& op) {
        x = (*this + op).x;
        return *this;
    }

    modint<mod> operator-(const modint<mod>& op) const {
        return *this + (-op);
    }

    modint<mod>& operator-=(const modint<mod>& op) {
        x = (*this - op).x;
        return *this;
    }

    modint<mod> operator*(const modint<mod>& op) const {
        return modint<mod>(x * op.x % mod);
    }

    modint<mod>& operator*=(const modint<mod>& op) {
        x = (*this * op).x;
        return *this;
    }

    modint<mod> pow(const long long n) const {
        if (n == 0) {
            return modint<mod>(1);
        }
        modint<mod> sq = pow(n / 2);
        if (n & 1) {
            return (*this) * sq * sq;
        } else {
            return sq * sq;
        }
    }

    modint<mod> inverse() const {
        return pow(mod - 2);
    }

    modint<mod> operator/(const modint<mod>& op) const {
        return (*this) * op.inverse();
    }

    modint<mod>& operator/=(const modint<mod>& op) {
        x = (*this / op).x;
        return *this;
    }

    friend modint<mod> operator/(const long long dividend, const modint<mod>& divisor) {
        return modint<mod>(dividend) / divisor;
    }

    static long long non_ord(long long x) {
        while (x % mod == 0) {
            x /= mod;
        }
        return x;
    }

    // returns n! / mod^(sum(ord(i))
    // normally equals to n!.
    static modint<mod> factorial(const long long n) {
        static vector<modint<mod>> cache(1, 1);
        while (cache.size() <= n) {
            modint<mod> next = cache.back() * non_ord(cache.size());
            cache.push_back(next);
        }
        return cache[n];
    }

    // returns mod^(sum(ord(i)) / n!
    static modint<mod> invfact(const long long n) {
        static vector<modint<mod>> cache(1, 1);

        while (cache.size() <= n) {
            modint<mod> next = cache.back() / non_ord(cache.size());
            cache.push_back(next);
        }
        return cache[n];
    }

    static long long ordfact(const long long n) {
        static vector<long long> cache(1, 0);

        while (cache.size() <= n) {
            long long x = cache.size();
            long long ord_n = 0;
            while (x % mod == 0) {
                x /= mod;
                ord_n++;
            }
            cache.push_back(cache.back() + ord_n);
        }
        return cache[n];
    }

    static modint<mod> combination(const long long n, const long long k) {
        if (k < 0 || n < k) {
            return modint<mod>(0);
        }

        if (ordfact(n) > ordfact(k) + ordfact(n - k)) {
            return modint<mod>(0);
        }

        if (n < 1e7) {
            return factorial(n) * invfact(k) * invfact(n - k);
        }

        modint<mod> ret = 1;
        for (int i = 1; i <= k; ++i) {
            ret = ret * modint<mod>(n - i + 1) / modint<mod>(i);
        }
        return ret;
    }
};

typedef modint<998244353> mint;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    li k;
    cin >> s >> k;

//    s = string(150, '0') + string(150, '1');
//    k = 1e9;

    li cnt = 0;
    vector<li> cnts;
    for (char i : s) {
        if (i == '0') {
            cnts.push_back(cnt);
            cnt = 0;
        } else {
            cnt++;
        }
    }
    cnts.push_back(cnt);
    reverse(cnts.begin(), cnts.end());

    const li n = cnts.size();
    const li ones = s.size() - (cnts.size() - 1);
    k = min(k, ones);
    vector<vector<vector<mint>>> dp(n + 1, vector<vector<mint>>(ones + 1, vector<mint>(k + 1, 0)));
    // dp[fixed][carry][used k]
    dp[0][0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        const li cur_zeros = cnts[i - 1];
        for (int carry = 0; carry <= ones; ++carry) {
            for (int to_k = 0; to_k <= k; ++to_k) {
                for (int new_zeros = 0; new_zeros <= ones; ++new_zeros) {
                    const li consume = new_zeros - cur_zeros;
                    const li prev_carry = carry + consume;
                    if (prev_carry < 0 || prev_carry > ones) {
                        continue;
                    }
                    const li prev_k = to_k - max(0LL, -consume);
                    if (prev_k < 0 || prev_k > k) {
                        continue;
                    }
                    dp[i][carry][to_k] += dp[i - 1][prev_carry][prev_k];
                }
//                cerr << i << " " << carry << " " << to_k << " " << dp[i][carry][to_k].x << endl;
            }
        }
    }

    mint ans = 0;
    for (int i = 0; i < k + 1; ++i) {
        ans += dp[n][0][i];
    }
    cout << ans.x << endl;
    return 0;
}

Measured memory_bytes: 31052