#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;
//typedef tree<
//        pair<long long, int>, // change type
//        null_type,
//        less<pair<long long, int> >, // change type
//        rb_tree_tag,
//        tree_order_statistics_node_update>
//        ordered_set;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;


vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifdef LOCAL
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) ;
#endif


typedef long long ll;
typedef long double ld;
#define rep(i, start, end) for(int i = start; i < end; ++i)
#define sz(x) (int)((x).size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define clr(d, v) memset(d, v, sizeof(d))
#define pii pair<int, int>
#define X first
#define Y second
//#define debug(x) cerr << #x << " : " << (x) << " "
const double PI = 3.14159265358979323846;
const double eps = (1e-9);
//int isGreater(long double x, long double y)
//{
//    if (abs(x - y) < eps)
//        return 0;
//    if (x > y)
//        return 1;
//    return -1;
//}

const int MOD = 998244353;
int add(int x, int y)
{
    x += y;
    if (x >= MOD)
        x -= MOD;
    return x;
}

int mult(int x, int y)
{
    return (1LL * x * y)%MOD;
}

const int MAX_N = 302;
int mem[MAX_N][MAX_N][MAX_N][2];
string s;
int k;
vector<int> a;
int solve(int i, int have, int totalDone, bool added)
{
    if (i == -1)
        return have == 0 && totalDone <= k;
    int &ret = mem[i][have][totalDone][added];
    if (~ret)
        return ret;
    ret = solve(i - 1, have, totalDone, false);
    if (!added)
    {
        for (int send = 1; send <= a[i] && send + totalDone <= k; ++send)
            ret = add(ret, solve(i - 1, have + send, totalDone + send, false));
    }
    if (have)
    {
        ret = add(ret, solve(i, have - 1, totalDone, true));
    }
    return ret;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
//    freopen("AC.txt", "w", stdout);
#endif
    cin >> s >> k;
    while(!s.empty() && s.back() == '0')
        s.pop_back();
    while(!s.empty() && s[0] == '1')
        s.erase(s.begin());
    if (s.empty())
    {
        cout << 1 << '\n';
        return 0;
    }

    a.push_back(0);
    for (int i = 1; i < sz(s); )
    {
        int cnt = 0;
        while(i < sz(s) && s[i] == '1')
        {
            cnt++;
            i++;
        }
        a.push_back(cnt);
        i++;
    }

    clr(mem, -1);
    cout << solve(sz(a) - 1, 0, 0, false);

}

Measured memory_bytes: 218872