//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
//#pragma GCC optimize("unroll-loops")

#ifdef __APPLE__
    # include <iostream>
    # include <cmath>
    # include <algorithm>
    # include <stdio.h>
    # include <cstdint>
    # include <cstring>
    # include <string>
    # include <cstdlib>
    # include <vector>
    # include <bitset>
    # include <map>
    # include <queue>
    # include <ctime>
    # include <stack>
    # include <set>
    # include <list>
    # include <random>
    # include <deque>
    # include <functional>
    # include <iomanip>
    # include <sstream>
    # include <fstream>
    # include <complex>
    # include <numeric>
    # include <immintrin.h>
    # include <cassert>
    # include <array>
    # include <tuple>
    # include <unordered_map>
    # include <unordered_set>
    # include <thread>
#else
    # include <bits/stdc++.h>
#endif

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define files(name) name!=""?freopen(name".in","r",stdin),freopen(name".out","w",stdout):0
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define elif else if
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;
#define int long long

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;

const int arr=2e5+10;
const int ar=2e3+10;
const ld pi=acos(-1);
const ld eps=1e-10;
const ll md=1e9+7;
const ll inf=1e18+10;

///---program start---///

#define md (ll)(998244353ll)

#define ar (int)(300+10)

void inc(int& a,int b)
{
    a+=b;
    if (a>=md){
        a-=md;
    }
}

int dp[2][ar][ar];

vi get_kek(string s)
{
    vi res(0);
    int cur=0;
    for (auto i:s){
        if (i=='0'){
            res.pb(cur);
            cur=0;
        }
        else{
            cur++;
        }
    }
    return res;
}

int suf_sum[arr];

bool debug=0;

signed main()
{
    #ifdef __APPLE__
        files("barik");
        freopen("debug.txt","w",stderr);
    #endif

    string s;
    int k;
    if (!debug) {
        cin >> s >> k;
    }
    else{
        for (int i=0;i<150;i++){
            s+="01";
        }
        k=1e9;
    }
    while (!s.empty() && s[0]=='1'){
        s.erase(s.begin());
    }
    s.pb('0');
    vi a = get_kek(s);
    for (int i=len(a)-1;i>=0;i--){
        suf_sum[i]=suf_sum[i+1]+a[i];
    }

    int cur=0;
    dp[cur][0][0]=1;
    for (int i=0;i<len(a);i++){
        for (int j=0;j<ar;j++){
            for (int l=0;l<ar;l++){
                dp[cur^1][j][l]=0;
            }
        }
        for (int j=0;j<=suf_sum[i];j++){
            for (int l=0;l<=len(s);l++){
                if (!dp[cur][j][l]){
                    continue;
                }

                for (int cur_to_pick=0;cur_to_pick<=a[i];cur_to_pick++){
                    if (j>=cur_to_pick) {
                        inc(dp[cur ^ 1][j - cur_to_pick][l],dp[cur][j][l]);
                    }
                }
                for (int cur_to_set=1;cur_to_set+j<=suf_sum[i+1];cur_to_set++){
                    inc(dp[cur^1][j + cur_to_set][l + cur_to_set],dp[cur][j][l]);
                }
            }
        }

        cur^=1;
    }

    int ans=0;
    for (int i=0;i<=len(s);i++){
        if (i<=k){
            inc(ans,dp[cur][0][i]);
        }
    }

    cout<<ans<<"\n";
}


Measured memory_bytes: 5148