// M
#include<bits/stdc++.h>
using namespace std;
const int N = 303, Mod = 998244353;
int n, k, C[N], dp[N][N][N];
inline void Add(int &a, int b)
{
	a += b;
	if (a >= Mod)
		a -= Mod;
}
int main()
{
	string S;
	cin >> S >> k;
	S = "0" + S;
	for (int i = 0; i < (int)S.size();)
	{
		int r = i + 1;
		while (r < (int)S.size() && S[r] == '1')
			r ++;
		C[n ++] = r - i - 1;
		i = r;
	}
	k = min(k, (int)S.size());
	dp[n][0][0] = 1;
	int sm = 0;
	for (int i = n - 1; ~ i; sm += C[i], i --)
		for (int j = sm; j >= 0; j --)
		{
			for (int h = 0; h <= k; h ++)
				Add(dp[i][j][h], dp[i][j + 1][h]),
				Add(dp[i][j][h], dp[i + 1][j][h]);
			for (int h = 0; h <= k; h ++)
				for (int df = 1; df <= C[i]; df ++)
					Add(dp[i][j + df][h + df], dp[i + 1][j][h]);
		}
	int tot = 0;
	for (int h = 0; h <= k; h ++)
		Add(tot, dp[0][0][h]);
	return !printf("%d\n", tot);
}

#include<stdio.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int mod = 1e9+7;
void ad(int &x,int y) { x+=y; if(x>=mod)x-=mod; }
int zy[8][2] = {{6,1},{3,2},{2,2},{4,1},{3,3},{6,1},{7,5},{6,6}};
char ss[300005];
int n;
int dp[300005][8];
int main() {
	scanf("%s",&ss[1]);
	n = strlen(ss+1);
	dp[0][0] = 1;
	for(int i=0;i<n;i++) {
		for(int j=0;j<8;j++) {
			if(ss[i+1]!='0') ad(dp[i+1][zy[j][1]],dp[i][j]);
			if(ss[i+1]!='1') ad(dp[i+1][zy[j][0]],dp[i][j]);
		}
	}
	int ans = (dp[n][1] + dp[n][2])%mod;
	printf("%d",ans);
}