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<bits/stdc++.h>
using namespace std;

long long mod = 998244353;

int main() {
  
  string S;
  long long K,N;
  cin >> S >> K;
  
  N = S.size();
  
  long long now = 0;
  long long n1 = 0;
  
  vector<long long> S_1(300,0);
  
  for (int i=0; i<N; i++) {
    if (S[i] == '0') {
      now++;
    }
    else {
      S_1[now]++;
      n1++;
    }
  }
  
  if (S[N-1] == '1') {
    now++;
  }
  
  K = min(n1,K);
  
  vector<vector<vector<long long>>> dp(now+1,vector<vector<long long>> (K+1,vector<long long> (K+1,0)));
  
  dp[now][K][0] = 1;
  
  
  n1 = 0;
  
  for (int i=now-1; i>=0; i--) {
    n1 += S_1[i];
    for (int j=max(0ll,K-n1); j<=K; j++) {
      for (int l=0; l<=n1; l++) {
        if (j+l > K) break;
        for (int m=l; j+m <= K; m++) {
          dp[i][j][l] += dp[i+1][j][m];
          dp[i][j][l] %= mod;
        }
        for (int m=1; m<=S_1[i]; m++) {
          if (j+m > K) break;
          if (l < m) break;
          dp[i][j][l] += dp[i+1][j+m][l-m];
          dp[i][j][l] %= mod;
        }
      }
    }
  }
  
  long long ans = 0;
  
  for (int i=0; i<=K; i++) {
    ans += dp[0][i][0];
    ans %= mod;
  }
  
  cout << ans << endl;
  
  return 0;
  
}