#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>
#include <complex>
#include <assert.h>

using namespace std;
typedef long long ll;
#define endl '\n'

template<typename T>
inline bool chmin(T& x, T a) {
	if (x >= a) { x = a; return true; }
	return false;
}

template<typename T>
inline bool chmax(T& x, T a) {
	if (x <= a) { x = a; return true; }
	return false;
}

/////////////         modの計算

#define MOD_IS_PRIME
const ll mod = 998244353LL;

class modlong {
public:
	modlong() { x = 0; }
	modlong(ll num) { x = adjust(num); }
	inline operator ll() const { return x; }
	inline bool operator ==(ll num) { return this->x == num; }
	inline bool operator !=(ll num) { return !(*this == num); }
	inline void operator = (ll num) { x = adjust(num); }
	inline void operator += (ll num) { x = adjust(x + num); }
	inline void operator ++() { this->operator+=(1); }
	inline modlong operator + (ll num) const { modlong m(this->x); m += num; return m; }
	inline void operator -= (ll num) { x = adjust(x - num); }
	inline void operator --() { this->operator-=(1); }
	inline modlong operator - (ll num) { modlong m(this->x); m -= num; return m; }
	inline void operator *= (ll num) { x = adjust(x * num); }
	inline modlong operator * (ll num) { modlong m(this->x); m *= num; return m; }
	inline void operator /= (ll num);
	inline modlong operator / (ll num);
private:
	inline ll adjust(ll a) {
		if (a >= mod) { return a % mod; }
		if (a < 0) { return mod - 1 + ((a + 1) % mod); }
		return a;
	}
	ll x;
};
inline modlong mod_inv(modlong a) {
	const ll inv_max = 300000;
	static vector<ll> inv;
	if (inv.size() == 0) {
		inv.resize(inv_max);
		for (int i = 0; i < inv_max; i++) {
			if (i <= 1) { inv[i] = i; }
			else { inv[i] = ((mod - mod / i) * inv[mod % i]) % mod; }
		}
	}
	ll p = mod, q = a, r;
	modlong m = 0, n = 1, c;
	while (1) {
		if (q < inv_max) { return n * inv[q]; }
		c = p / q; r = p % q; c = m - n * c;
		p = q, q = r; m = n, n = c;
	}
}
inline modlong mod_div(modlong a, modlong b) { return a * mod_inv(b); }
inline void modlong::operator /=(ll num) { x = mod_div(*this, num); }
inline modlong modlong::operator /(ll num) { modlong m(this->x); m /= num; return m; }

inline modlong mod_pow(modlong x, ll n) {
	if (n < 0) { x = mod_inv(x); n = -n; }
#ifdef MOD_IS_PRIME
	n = n % (mod - 1);
#endif
	modlong temp = x, ans = 1;
	while (n > 0) {
		if (n & 1) { ans *= temp; }
		temp *= temp;
		n >>= 1;
	}
	return ans;
}
inline modlong mod_log(modlong a, modlong x) {
	ll A = sqrt(mod);
	ll B = (mod + A - 1) / A;
	map<ll, ll> mp1, mp2;
	ll p0 = a;
	ll q0 = mod_pow(a, -A);
	ll p = 1;
	ll q = x;
	for (int i = 0; i < A; i++) {
		mp1.insert({ p, i });
		p = (p * p0) % mod;
	}
	for (int i = 0; i < B; i++) {
		mp2.insert({ q, A * i });
		q = (q * q0) % mod;
	}
	auto itr1 = mp1.begin();
	auto itr2 = mp2.begin();
	while (itr1 != mp1.end() && itr2 != mp2.end()) {
		if (itr1->first < itr2->first) {
			itr1++;
		}
		else if (itr1->first == itr2->first) {
			return itr1->second + itr2->second;
		}
		else {
			itr2++;
		}
	}
	return 0;
}

inline modlong mod_factorial(modlong n, bool inverse = false) {
	static vector<ll> factorial, factorial_inv;

	ll M = factorial.size();
	if (M <= n) {
		if (M == 0) { factorial.push_back(1); factorial_inv.push_back(1); M++; }
		if (M == 1) { factorial.push_back(1); factorial_inv.push_back(1); M++; }

		for (ll i = M; i <= n; i++) {
			factorial.push_back((factorial.back() * i) % mod);
			factorial_inv.push_back((factorial_inv.back() * mod_inv(i)) % mod);
		}
	}
	if (inverse == true) { return factorial_inv[n]; }
	else { return factorial[n]; }
}
inline modlong mod_combination(modlong n, modlong r) {
	assert(r <= n);
	return mod_factorial(n) * mod_factorial(n - r, true) * mod_factorial(r, true);
}

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

	string S; cin >> S;
	ll K; cin >> K;
	vector<ll> v;
	ll count = 0;
	for (int i = 0; i <= S.size(); i++) {
		if (i == S.size() || S[i] == '0') {
			v.push_back(count);
			count = 0;
		}
		else {
			count++;
		}
	}

	ll M = 0;
	ll N = v.size();

	for (int i = 0; i < N; i++) {
		M += v[i];
	}

	chmin(M, K);

	vector<vector<vector<modlong>>> dp(N);
	for (int i = 0; i < N; i++) {
		dp[i].resize(M + 1);
		for (int j = 0; j <= M; j++) {
			dp[i][j].resize(M + 1, 0);
		}
	}

	for (int j = 0; j <= min(v[N - 1], M); j++) {
		dp[N - 1][j][j] = 1;
	}
	for (int i = N - 2; i >= 0; i--) {
		// 奪うフェーズ
		for (int j0 = 0; j0 <= M; j0++) {
			modlong sum = 0;
			for (int j = j0; j <= M; j++) {
				int k = j - j0;
				sum += dp[i + 1][j][k];
				if (k - v[i] - 1 >= 0) {
					sum -= dp[i + 1][j - v[i] - 1][k - v[i] - 1];
				}
				dp[i][j][k] = sum;
			}
		}

		// 与えるフェーズ
		for (int j = 0; j <= M; j++) {
			modlong sum = 0;
			for (int k = j; k >= 0; k--) {
				dp[i][j][k] += sum;
				sum += dp[i + 1][j][k];
			}
		}
	}

	modlong ans = 0;
	for (int j = 0; j <= M; j++) {
		ans += dp[0][j][0];
	}
	cout << (ll)ans << endl;

	return 0;
}

Measured memory_bytes: 30440