#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) static_cast<int>((x).size())

using LL = long long;
template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
    : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
    : vector<T>(args...) {}
};

template<class T>
inline bool asMn(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int nex(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int pre(int i, int n) { return !i ? n - 1 : i - 1; }

const int mod = 998244353;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

struct ModInt {
  int a;
  ModInt(int _a = 0)
    : a(_a) {}
  friend istream& operator>>(istream& in, ModInt& _) {
    in >> _.a;
    return in;
  }
  friend ostream& operator<<(ostream& out, const ModInt& _) {
    out << _.a;
    return out;
  }

  bool operator<(const ModInt& _) const { return a < _.a; }
  bool operator>(const ModInt& _) const { return a > _.a; }
  bool operator<=(const ModInt& _) const { return a <= _.a; }
  bool operator>=(const ModInt& _) const { return a >= _.a; }
  bool operator==(const ModInt& _) const { return a == _.a; }
  bool operator!=(const ModInt& _) const { return a != _.a; }
  bool operator!() const { return !a; }

  ModInt operator+(const ModInt& _) const {
    int ret = a + _.a;
    return ret < mod ? ModInt(ret) : ModInt(ret - mod);
  }
  ModInt operator-(const ModInt& _) const { return *this + ModInt(mod - _.a); }
  ModInt operator*(const ModInt& _) const { return ModInt((int)((LL)a * _.a % mod)); }
  ModInt operator/(const ModInt& _) const { return *this * _.binPow(mod - 2); }
  ModInt& operator+=(const ModInt& _) { return *this = *this + _; }
  ModInt& operator-=(const ModInt& _) { return *this = *this - _; }
  ModInt& operator*=(const ModInt& _) { return *this = *this * _; }
  ModInt& operator/=(const ModInt& _) { return *this = *this / _; }
  ModInt& operator++() { return *this = *this + ModInt(1); }
  ModInt& operator--() { return *this = *this - ModInt(1); }
  ModInt operator-() const { return ModInt() - *this; }

  template<class T>
  ModInt binPow(T exponent) const {
    ModInt ret(1), c = *this;
    for (; exponent; exponent >>= 1, c *= c) if (exponent & 1) ret *= c;
    return ret;
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  string s; int mx; cin >> s >> mx;

  vec<int, 1> n0(sz(s) + 1), cnt(sz(s) + 1);
  for (int i = 0; i < sz(s); ++i) {
    n0[i + 1] = n0[i] + (s[i] == '0');
    if (s[i] == '1') {
      ++cnt[n0[i + 1]];
    }
  }

  vec<ModInt, 3> f(sz(s) + 1, n0.back() + 1, sz(s) - n0.back() + 1);
  vec<ModInt, 3> g(sz(s) + 1, n0.back() + 1, sz(s) - n0.back() + 1);
  vec<ModInt, 3> h(sz(s) + 1, n0.back() + 1, sz(s) - n0.back() + 1);
  f[0][0][0] = ModInt(1);
  for (int j = 0; j < sz(f[0]); ++j) {
    for (int k = 0; k < sz(f[0][j]); ++k) {
      g[0][j][k] = h[0][j][k] = f[0][j][k];
    }
  }
  for (int i = 1; i <= sz(s); ++i) {
    for (int j = 1; j <= n0[i]; ++j) {
      for (int k = 0; k <= min(sz(s) - n0.back(), i - 1); ++k) {
        if (i - 1 - cnt[j - 1] >= 0 && k - cnt[j - 1] >= 0) {
          f[i][j][k] += g[i - 1 - cnt[j - 1]][j - 1][k - cnt[j - 1]];
          f[i][j][k] -= h[i - 1 - cnt[j - 1]][j - 1][k - cnt[j - 1]];
        }
        f[i][j][k] += h[i - 1][j - 1][k];
      }
    }

    for (int j = 0; j < sz(f[i]); ++j) {
      for (int k = 0; k < sz(f[i][j]); ++k) {
        g[i][j][k] = h[i][j][k] = f[i][j][k];
        g[i][j][k] += g[i - 1][j][k];
        if (k) {
          h[i][j][k] += h[i - 1][j][k - 1];
        }
      }
    }
  }

  ModInt ans;
  for (int k = 0; k <= sz(s) - n0.back(); ++k) {
    if (sz(s) - n0.back() - k <= mx) {
      if (sz(s) - cnt[n0.back()] >= 0 && k - cnt[n0.back()] >= 0) {
        ans += g[sz(s) - cnt[n0.back()]][n0.back()][k - cnt[n0.back()]];
        ans -= h[sz(s) - cnt[n0.back()]][n0.back()][k - cnt[n0.back()]];
      }
      ans += h[sz(s)][n0.back()][k];
    }
  }

  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 89568