#include "bits/stdc++.h"
#define ll long long
#define lld long double
#define MOD 998244353
#define inf 1000000000000000000ll
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll power(ll x,ll y, ll md=MOD){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}
 
using namespace std;

#define endl '\n'
#define int ll


int lcm(int a, int b) {
	int g = __gcd(a,b);
	int ans = a/g;
	ans *= b;
	return ans;
}

string s;
int k;

int dp[305][305][305];
int pre[305][305][305];
int pre1[305][305][305];
vector<int> v;

// int solve(int index, int out, int total) {
// 	if(out<0 || out>3) return 0;

// 	if(index==v.size()) {
// 		if(out==0) return 1;
// 		else return 0;
// 	}

// 	if(dp[index][out]!=-1) return dp[index][out];
// 	int ans = 0;

// 	// Consumer
// 	for(int i=0;i<=300;i++) {
// 		ans += solve(index+1,out+i, total);
// 		ans %= MOD;
// 	}

// 	// Producer
// 	for(int i=1;i<=v[index];i++) {
// 		ans += solve(index+1,out-i, total+i);
// 		ans %= MOD;
// 	}

// 	cout<<index<<" "<<out<<" -- "<<ans<<endl;
// 	return dp[index][out] = ans;
// }

signed main() {
	fast;

	cin>>s;
	cin>>k;

	int cur = 0;
	int n = s.size();
	k = min(k, n);

	for(int i=0;i<n;i++) {
		if(s[i]=='0') {v.pb(cur);cur=0;}
		else cur++;
	}
	v.pb(cur);

	for(int i=0;i<=300;i++) pre[v.size()][0][i] = 1, pre1[v.size()][0][0] = 1;

	int ff = 0;

	for(int i=(int)v.size()-1;i>=0;i--) {
		for(int tot=k;tot>=0;tot--) {

			for(int out=0;out<=300;out++) {
				int ans = 0;

				int sum = pre[i+1][tot][300] - ((out==0)?0:pre[i+1][tot][out-1]);
				// if(i==2 && tot==0 && out==0) cout<<"$$"<<sum<<endl;

				ans += sum;
				ans %= MOD;

				if(tot>=out) sum = ((out-(v[i]) < 0) ? pre1[i+1][tot-out][0]: pre1[i+1][tot-v[i]][out-v[i]]) - pre1[i+1][tot][out];
				else sum = ((tot-(v[i]) < 0) ? pre1[i+1][0][out-tot]: pre1[i+1][tot-v[i]][out-v[i]]) - pre1[i+1][tot][out];
				// if(i==2 && tot==0 && out==0) cout<<"$$"<<sum<<" "<<v[i]<<endl;

				ans += sum;
				ans %= MOD;

				if(out!=0) {
					pre[i][tot][out] = (ans + pre[i][tot][out-1])%MOD;
				}
				else {
					pre[i][tot][out] = ans;
				}

				if(out!=300) {
					pre1[i][tot][out] = (ans + pre1[i][tot+1][out+1])%MOD;
				}
				else {
					pre1[i][tot][out] = ans;
				}

				// cout<<"#"<<i<<" "<<tot<<" "<<out<<" -- "<<ans<<endl;

				if(i==0&&tot<=k&&out==0) ff += ans;
				ff %= MOD;
			}
		}
	}

	ff += MOD;
	ff %= MOD;
	cout<<ff;

}
const int LG = 21;
const int FN = 400005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vi;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};

ll inq(ll x, ll y)
{
    if (!y) re 1 % MOD;
    ll l = inq(x, y / 2);
    if (y % 2) re l * l % MOD * x % MOD;
    re l * l % MOD;
}

ll rev(ll x)
{
    return inq(x, MOD - 2);
}

bool __precomputed_combinatorics = 0;
vector<ll> __fact, __ufact, __rev;

void __precompute_combinatorics()
{
    __precomputed_combinatorics = 1;
    __fact.resize(FN);
    __ufact.resize(FN);
    __rev.resize(FN);
    __rev[1] = 1;
    for (int i = 2; i < FN; i++) __rev[i] = MOD - __rev[MOD % i] * (MOD / i) % MOD;
    __fact[0] = 1, __ufact[0] = 1;
    for (int i = 1; i < FN; i++) __fact[i] = __fact[i - 1] * i % MOD, __ufact[i] = __ufact[i - 1] * __rev[i] % MOD;
}

ll fact(int x)
{
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[x];
}

ll cnk(int n, int k)
{
    if (k < 0 || k > n) return 0;
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[n] * __ufact[n - k] % MOD * __ufact[k] % MOD;
}

ll dp[200][10];
ll se[10];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    se[0] = 1;
    se[1] = 1;
    se[2] = 2;
    se[3] = 3;
    se[4] = 5;
    se[5] = 8;
    se[6] = 13;
    se[7] = 21;
    int h, w, k;
    cin >> h >> w >> k;
    dp[0][1] = 1;
    for (int i = 0; i < h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * se[j - 1] % MOD * se[w - j]) % MOD;
            if (j - 1 >= 1) dp[i + 1][j - 1] = (dp[i + 1][j - 1] + dp[i][j] * se[j - 2] % MOD * se[w - j]) % MOD;
            if (j + 1 <= w) dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * se[j - 1] % MOD * se[w - j - 1]) % MOD;
        }
    }
    cout << dp[h][k];
}

/* Note:
Check constants at the beginning of the code.
    N is set to 4e5 but be careful in problems with large constant factor.
    Setting N in every problem is more effective.
Check corner cases.
    N = 1
No def int long long for now.
Add something here.
*/
