#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:256000000")
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<sstream>
#include<utility>
#include<map>
#include<ctime>
#include<cstdio>
#include<cassert>
#include<functional>
#include<unordered_map>




using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;
typedef pair<double, double> pdd;

#define show(x) cerr << x
#define debug(x) show(#x << ": " << (x) << endl)

const long double PI = 3.14159265358979323846;
const long double eps = 1e-5;
const int INF = numeric_limits<int>::max();
const ll LINF = numeric_limits<ll>::max();
const ll mod = 998244353;
const ll N = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000;



void solve() {
    string s;
    int k;
    cin >> s >> k;
    vector<int> p;
    s = "0" + s + "0";
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '0') {
            p.push_back(i);
        }
    }
    vector<int> a;
    for (int i = 1; i < p.size(); ++i) {
        a.push_back(p[i] - p[i - 1] - 1);
    }
    int ones = (int)s.size() - (int)p.size();
    k = min(k, ones);
    vector<vector<int> > d(ones + 1, vector<int> (k + 1, 0));
    vector<vector<int> > dd;
    d[0][0] = 1;
    for (int i = a.size() - 1; i >= 0; --i) {
        dd.assign(ones + 1, vector<int> (k + 1, 0));
        vector<vector<ll> > pr(ones + 1, vector<ll>(k + 1, 0));
        for (int i1 = 0; i1 <= ones; ++i1) {
            for (int i2 = 0; i2 <= k; ++i2) {
                pr[i1][i2] += d[i1][i2];
                if ((i1 > 0) && (i2 > 0))
                    pr[i1][i2] += pr[i1 - 1][i2 - 1];
                pr[i1][i2] %= mod;
            }
        }
        for (int i1 = 0; i1 <= ones; ++i1) {
            for (int i2 = 0; i2 <= k; ++i2) {
                if ((i1 >= a[i] + 1) && (i2 >= a[i] + 1))
                    dd[i1][i2] = pr[i1][i2] - pr[i1 - a[i] - 1][i2 - a[i] - 1];
                else 
                    dd[i1][i2] = pr[i1][i2];
                dd[i1][i2] %= mod;
                dd[i1][i2] += mod;
                dd[i1][i2] %= mod;
            }
        }
        for (int i2 = 0; i2 <= k; ++i2) {
            ll add = 0;
            for (int i1 = ones; i1 >= 0; --i1) {
                
                dd[i1][i2] += add;
                dd[i1][i2] %= mod;
                add += d[i1][i2];
                add %= mod;
            }
        }
        /*
        for (int nv = a[i] + 1; nv < s.size() + 1; ++nv) {
            for (int i1 = 0; i1 + nv - a[i] <= ones; ++i1) {
                for (int i2 = 0; i2 <= k; ++i2) {
                    dd[i1][i2] += d[i1 + nv - a[i]][i2]; 
                    dd[i1][i2] %= mod;
                }
            }
        }*/
        swap(d, dd);
    }
    ll res = 0;
    for (int i = 0; i <= k; ++i)
        res += d[0][i];
    res %= mod;
    cout << res << endl;

}

//#define LOCAL

int main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    
    solve();

#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif	
    return 0;
}

Measured memory_bytes: 4316