#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <memory>
#include <string>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>
#include <list>
#include <forward_list>
#include <algorithm>
#include <regex>
#include <cmath>
#include <map>
#include <iterator>
#include <climits>
#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <array>
#include <valarray>
#include <complex>
#include <random>
#include <functional>
#include <cassert>
#include <chrono>
#include <memory>

using namespace std;

#define int long long
//region TEMPLATE
////@formatter:off
#define double long double
typedef long long ll;
typedef unsigned long long ull;
template<typename T>void __read(T &a) { cin >> a; }
template<typename T, typename ... Args> void __read(T &a, Args &... args) { cin >> a;__read(args...);}
#define make(t, ...) t __VA_ARGS__; __read(__VA_ARGS__)
#define makev(a, n) VI a(n); FOR(n) cin >> a[i]
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FORIT(p) for(auto it = p.begin(); it != p.end(); it++)
#define FOR(b) for(signed i = 0; i <(b); i++)
#define FORE(i, l, r) for(int i = (l); i < (r); i++)
#define NFOR(i, n) for(int i = (((int) n)-1); i >= 0; i--)
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PPII;
constexpr ll M7 = 1000000007ll;
constexpr ll M9 = 1000000009ll;
constexpr ll MFFT = 998244353ll;
template<class T> void outv(T &a) { for (auto &x : a) cout << x << ' '; }
static mt19937 rnd(static_cast<unsigned>(chrono::steady_clock::now().time_since_epoch().count())); // NOLINT(cert-err58-cpp)
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr)); // NOLINT(cert-err58-cpp,cppcoreguidelines-interfaces-global-init)
////@formatter:on
//endregion

const int N = 301;
VI dp[N][N][N];

int solve1(string s, int k){
    while (s.back() == '0') {
        s.pop_back();
    }
    while (!s.empty() && s[0] == '1') {
        s.erase(s.begin());
    }
    if (s.empty() || k == 0) {
        return 1;
    }
    s.push_back('0');
    int n = s.length();


    VI pos[2];
    for (int i = 0; i < n; ++i) {
        pos[s[i] - '0'].push_back(i);
    }
    VI prevZ(n), grSz(n);
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] == '0') {
            prevZ[i] = find(ALL(pos[0]), i) - pos[0].begin();
        } else {
            prevZ[i] = prevZ[i + 1];
            grSz[pos[0][prevZ[i]]]++;
        }
    }

    for (int i = 0; i < pos[1].size(); ++i) {
        for (int j = 0; j < pos[0].size(); ++j) {
            for (int m = 0; m <= pos[1].size(); ++m) {
                dp[i][j][m].assign(grSz[pos[0][j]] + 1, 0);
            }
        }
    }
    for (int j = 0; j < pos[0].size() && j < prevZ[pos[1][0]]; ++j) {
        dp[0][j][1][0] = 1;
    }
    dp[0][prevZ[pos[1][0]]][0][0] = 1;
    for (int i = 1; i < pos[1].size(); ++i) {
        for (int m = 0; m <= i; ++m) {
            int prSm = 0;
            for (int j = 0; j < pos[0].size() && j < prevZ[pos[1][i]]; ++j) {
                {
                    int f = dp[i][j][m].size() == 1;
                    dp[i][j][m + f][0] = (dp[i][j][m + f][0] + prSm) % MFFT;
                }
                prSm = (prSm + accumulate(ALL(dp[i - 1][j][m]), 0ll)) % MFFT;
                int dSz = dp[i][j][m].size();
                for (int d = 0; d + 2 < dSz; ++d) { // (d + 2) ???
                    dp[i][j][m][d + 1] = (dp[i][j][m][d + 1] + dp[i - 1][j][m][d]) % MFFT;
                }
                if (dSz > 1){
                    dp[i][j][m + 1][dSz - 1] = (dp[i][j][m + 1][dSz - 1] + dp[i - 1][j][m][dSz - 2]) % MFFT;
                }
                dp[i][j][m + 1][dSz - 1] = (dp[i][j][m + 1][dSz - 1] + dp[i - 1][j][m][dSz - 1]) % MFFT;
            }
            int j = prevZ[pos[1][i]];
            int dSz = dp[i][j][m].size();
            dp[i][j][m][0] = (dp[i][j][m][0] + prSm) % MFFT;//??
            for (int d = 0; d + 1 < dSz; ++d) {
                dp[i][j][m][d + 1] = (dp[i][j][m][d + 1] + dp[i - 1][j][m][d]) % MFFT;
            }
        }
    }
    int ans = 0;
    int lastI = pos[1].size() - 1;
    for (int j = 0; j < pos[0].size(); ++j) {
        for (int m = 0; m <= min((int) pos[1].size(), k); ++m) {
            for (int d = 0; d < dp[lastI][j][m].size(); ++d) {
                ans += dp[lastI][j][m][d];
            }
        }
    }
    return ans % MFFT;
}

int solve2(string s, int k){
    set<string> was;
    queue<pair<int, string>> q;
    q.emplace(0, s);
    was.insert(s);
    while(!q.empty()){
        auto [d, t] = q.front();
        q.pop();
        if (d >= k){
            break;
        }
        for(int i = 0; i < t.length(); ++i){
            if (t[i] == '0'){
                for(int j = i +1; j < t.length(); ++j){
                    if (t[j] == '1'){
                        auto tt = t;
                        tt.erase(tt.begin() + j);
                        tt.insert(tt.begin() + i, '1');
                        if (!was.count(tt)){
                            was.insert(tt);
                            q.emplace(d + 1, tt);
                        }
                    }
                }
            }
        }

    }
    return was.size();
}


int32_t main() {
//    const int n = 8;
//    for(int mask = 0; mask < (1 << n); ++mask){
//        string s = bitset<n>(mask).to_string();
//        for(int k = 0; k <= n; ++k){
//            int ans1 = solve1(s, k);
//            int ans2 = solve2(s, k);
//            if (ans1 != ans2){
//                cout << s << ' ' << k << endl;
//                cout << ans1 << ' ' << ans2 << endl;
//                exit(0);
//            }
//        }
//    }
//    cout << "OK\n";
//    exit(0);


    make(string, s);
    make(int, k);

    cout << solve1(s, k); //<< ' ' << solve2(s, k);

    return 0;
}

Measured memory_bytes: 846788