#include<bits/stdc++.h>
#define XX first
#define YY second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

const int B = 310;

template<ll mod>
struct ModInt{
  using M=ModInt;
  ll a;
  M& put(ll v){
    a=(v<mod)?v:v-mod;
    return *this;
  }
  ModInt(ll v=0){put(v%mod+mod);}
  M operator+(M x){return M().put(a+x.a);}
  M operator-(M x){return M().put(a+mod-x.a);}
  M operator*(M x){return M().put(a*x.a%mod);}
  M operator/(M x){return x.inv()*a;}
  M& operator+=(M x){return *this=*this+x;};
  M& operator-=(M x){return *this=*this-x;};
  M& operator*=(M x){return *this=*this*x;};
  M& operator/=(M x){return *this=*this/x;};
  bool operator==(M x){return a==x.a;}
  M pow(ll m) {
    M x=*this,res=1;
    while(m){
      if(m&1)res*=x;
      x*=x;
      m>>=1;
    }
    return res;
  }
  M inv(){return pow(mod-2);}
};
using mint = ModInt<998244353>;

int N;
string S;
int K;
mint dp[2][614][614];
mint naname[2][614][614];
mint tate[2][614][614];

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);

  cin >> S;
  cin >> K;
  N = S.size();
  int cnt = 0;
  rep(i, N) cnt += S[i] == '1';
  MN(K, cnt);

  vector<int> rems;
  cnt = 0;
  rep(i, N) {
    if (S[i] == '0') {
      rems.eb(cnt);
      cnt = 0;
    } else if (S[i] == '1') cnt++;
    else assert(0);
  }
  rems.eb(cnt);

  int dst = 1;
  int src = 0;
  int rem = rems.back(); rems.pop_back();
  rep(i, rem+1) {
    if (K < i) break;
    dp[src][i][K-i] = 1;
  }

  bool app = 0;
  rrep(i, N) {
    if (S[i] == '1') {
    } else if (S[i] == '0') {
      assert(rems.size());
      rem = rems.back(); rems.pop_back();
      rep(j, N+1) {
        rep(k, K+1) {
          tate[dst][j][k] = 0;
          naname[dst][j][k] = 0;
        }
      }

      rep(j, N+1) {
        rep(k, K+1) {
          tate[dst][j][k] += dp[src][j][k];
          tate[dst][j+1][k] -= dp[src][j][k];
        }
      }

      app = 1;
      if (app) {
        rep(j, N+1) {
          rep(k, K+1) {
            tate[dst][0][k] += dp[src][j][k];
            tate[dst][j][k] -= dp[src][j][k];
          }
        }
      }

      rep(j, N+1) {
        rep(k, K+1) {
          int d = min(k, rem);
          if (d == 0) continue;
          naname[dst][j+1][k-1] += dp[src][j][k];
          if (k-d-1 >= 0 && j+d+1 <= N) {
            naname[dst][j+d+1][k-d-1] -= dp[src][j][k];
          }
        }
      }

      rep(j, N+1) {
        rep(k, K+1) {
          tate[dst][j+1][k] += tate[dst][j][k];
        }
      }

      rep(tot, N+K+1) {
        rep(j, tot+1) {
          int k = tot - j;
          if (k >= 1) naname[dst][j+1][k-1] += naname[dst][j][k];
        }
      }
      
      rep(j, N+1) {
        rep(k, K+1) {
          dp[src][j][k] = tate[dst][j][k] + naname[dst][j][k];
        }
      }

      //rep(j, N+1) {
      //  rep(k, K+1) {
      //    cout << "dp[" << j << "][" << k << "]: " << dp[src][j][k].a << endl;
      //  }
      //}

      rem = 0;
    } else assert(0);
  }

  mint ans = 0;
  rep(k, K+1) {
    ans += dp[src][0][k];
    //cout << k << ": " << dp[src][0][k].a << endl;
  }
  cout << ans.a << endl;
}


Measured memory_bytes: 21284