Problem: Given is a string S consisting of `0` and `1`. Find the number of strings, modulo 998244353, that can result from applying the following operation on S between 0 and K times (inclusive):

* Choose a pair of integers i, j (1\leq i < j\leq |S|) such that the i-th and j-th characters of S are `0` and `1`, respectively. Remove the j-th character from S and insert it to the immediate left of the i-th character.

Constraints

* 1 \leq |S| \leq 300
* 0 \leq K \leq 10^9
* S consists of `0` and `1`.

Input

Input is given from Standard Input in the following format:


S K


Output

Find the number of strings, modulo 998244353, that can result from applying the operation on S between 0 and K times (inclusive).

Examples

Input

0101 1


Output

4


Input

01100110 2


Output

14


Input

1101010010101101110111100011011111011000111101110101010010101010101 20


Output

113434815

Solution (in CPP):

Solution:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cstdint>

int main() {
  constexpr std::int64_t kModulus = 998244353;
  std::string S;
  int K;
  std::cin >> S >> K;
  const int N = S.size();
  K = std::min(K, N);
  std::vector<int> zeros;
  for (int i = 0; i < N; ++i) {
    if (S[i] == '0') {
      zeros.push_back(i);
    }
  }
  const int num_zeros = zeros.size();
  if (num_zeros == 0 || num_zeros == N) {
    std::cout << 1 << std::endl;
    return 0;
  }
  zeros.push_back(N);
  std::vector<std::vector<std::vector<std::int64_t>>> mem(num_zeros + 1, std::vector<std::vector<std::int64_t>>(N + 1, std::vector<std::int64_t>(K + 1)));
  mem[num_zeros][N][0] = 1;
  for (int i = num_zeros - 1; i >= 0; --i) {
    for (int j = zeros[i]; j < N; ++j) {
      for (int k = std::max(j + 1, zeros[i + 1]); k <= N; ++k) {
        int m = std::max(0, (j - zeros[i]) - (k - zeros[i + 1]));
        for (int l = 0; l + m <= K; ++l) {
          mem[i][j][l + m] += mem[i + 1][k][l];
          mem[i][j][l + m] %= kModulus;
        }
      }
    }
  }
  std::int64_t sum = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= K; ++j) {
      sum += mem[0][i][j];
    }
  }
  std::cout << sum % kModulus << std::endl;
  return 0;
}