// -----------------------------------
// author   : MatsuTaku
// country  : Japan
// created  : 06/20/20 20:14:02
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

template <typename T, T MOD>
class modular {
 private:
  T val_;

 public:
  constexpr modular() : val_(0) {}
  constexpr modular(T v) : val_(v%MOD) {}
  constexpr modular& operator=(T v) { val_ = v%MOD; return *this; }

  constexpr T val() const { return val_; }
  constexpr modular operator+(modular x) const { return (val() + x.val())%MOD; }
  constexpr modular operator+=(modular x) { return *this = *this + x; }
  constexpr modular operator++() { return *this += 1; }
  constexpr modular operator++(int) { modular c = *this; ++(*this); return c; }
  constexpr modular operator-(modular x) const { return (val() + MOD - x.val())%MOD; }
  constexpr modular operator-=(modular x) { return *this = *this - x; }
  constexpr modular operator--() { return *this -= 1; }
  constexpr modular operator--(int) { modular c = *this; --(*this); return c; }
  constexpr modular operator*(modular x) const { return (val() * x.val())%MOD; }
  constexpr modular operator*=(modular x) { return *this = *this * x; }
  friend constexpr modular pow(modular x, T p) {
    modular t = 1;
    modular u = x;
    while (p) {
      if (p & 1)
        t *= u;
      u *= u;
      p >>= 1;
    }
    return t;
  }
  constexpr modular operator/(modular x) const { return *this * pow(modular{x}, MOD-2); }
  constexpr modular operator/=(modular x) { return *this = *this / x; }

  constexpr bool operator==(modular x) const { return val() == x.val(); }
  constexpr bool operator!=(modular x) const { return val() != x.val(); }
  constexpr bool operator<(modular x) const { return val() < x.val(); };
  constexpr bool operator<=(modular x) const { return val() <= x.val(); };
  constexpr bool operator>(modular x) const { return val() > x.val(); };
  constexpr bool operator>=(modular x) const { return val() >= x.val(); };

  friend std::ostream& operator<<(std::ostream& os, const modular& x) {
    return os << x.val();
  }
  friend std::istream& operator>>(std::istream& is, modular& x) {
    return is >> x.val_;
  }

};
using mint = modular<ll, 998244353>;

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

  string s; cin>>s;
  int k; cin>>k;

  vector<int> os;
  int co = 0;
  for (auto c:s) {
    if (c == '1')
      co++;
    else {
      os.push_back(co);
      co = 0;
    }
  }
  os.push_back(co);
  int n = os.size();
  int MAXK = min(accumulate(os.begin(), os.end(), 0), k);

  mint dp[2][MAXK+1][MAXK+1];
  for (int i = 0; i <= MAXK; i++)
    for (int j = 0; j <= MAXK; j++)
      dp[0][i][j] = 0;
  dp[0][0][0] = 1;
  int dpi = 0;
  for (int i = n-1; i >= 0; i--) {
    ++dpi;
    auto& nxt = dp[dpi%2];
    auto& pdp = dp[dpi%2^1];
    memcpy(&nxt, &pdp, sizeof(mint)*(MAXK+1)*(MAXK+1));
    // push
    for (int j = 1; j <= MAXK; j++) {
      mint rsum = 0;
      for (int l = 0; l <= j; l++) {
        nxt[j][l] += rsum;
        rsum += pdp[j][l];
      }
    }
    // pop
    if (os[i] == 0)
      continue;
    for (int l = 0; l <= MAXK; l++) {
      mint rsum = 0;
      for (int j = 0; j <= MAXK; j++) {
        nxt[j][l] += rsum;
        rsum += pdp[j][l];
        if (j-os[i] >= 0)
          rsum -= pdp[j-os[i]][l];
      }
    }
  }
  mint ans = 0;
  for (int l = 0; l <= MAXK; l++) {
    ans += dp[dpi%2][l][l];
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 4988