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;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_range(i, s, e) for (int i = (s); i < (int)(e); i++)
#define rep_rev(i, s, e) for (int i = (s)-1; i >= (int)(e); i--)
#define sort_vec(v) sort((v).begin(),(v).end())
typedef int64_t lint;
lint mod = 998244353;
// lint mod = 1000000007;
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

int app() {
  string s;
  int k;
  cin>>s>>k;
  int kmax=310;

  vector<int> a(s.length());
  int seg=0;
  rep_rev(j,s.length(),0){
    if(s[j]=='1') a[seg]++;
    else seg++;
  }
  seg++;

  vector<vector<vector<lint>>> dp(seg,
    vector<vector<lint>>(310,
      vector<lint>(kmax,0)
    )
  );
  dp[0][0][0]=1;
  int cmax=310;
  rep_range(i,1,seg){
    rep(c,cmax){
      rep(m,kmax){
        int dpi1cm=dp[i-1][c][m]%mod;
        if(dpi1cm==0) continue;
        rep_range(d,-c,a[i-1]+1){
          if(m+d>k) continue;
          dp[i][c+d][m+max(0,d)]+=dpi1cm;
        }
      }
    }
  }

  lint ans=0;
  rep(c,cmax)rep(m,kmax) ans+=dp[seg-1][c][m];
  return ans%mod;
}

int main(){cout<<app()<<endl;return 0;}