You are given a binary string (i. e. a string consisting of characters 0 and/or 1) s of length n. You can perform the following operation with the string s at most once: choose a substring (a contiguous subsequence) of s having exactly k characters 1 in it, and shuffle it (reorder the characters in the substring as you wish).

Calculate the number of different strings which can be obtained from s by performing this operation at most once.

Input

The first line contains two integers n and k (2 ≤ n ≤ 5000; 0 ≤ k ≤ n).

The second line contains the string s of length n, consisting of characters 0 and/or 1.

Output

Print one integer — the number of different strings which can be obtained from s by performing the described operation at most once. Since the answer can be large, output it modulo 998244353.

Examples

Input


7 2
1100110


Output


16


Input


5 0
10010


Output


1


Input


8 1
10001000


Output


10


Input


10 8
0010011000


Output


1

Note

Some strings you can obtain in the first example:

  * to obtain 0110110, you can take the substring from the 1-st character to the 4-th character, which is 1100, and reorder its characters to get 0110; 
  * to obtain 1111000, you can take the substring from the 3-rd character to the 7-th character, which is 00110, and reorder its characters to get 11000; 
  * to obtain 1100101, you can take the substring from the 5-th character to the 7-th character, which is 110, and reorder its characters to get 101. 



In the second example, k = 0 so you can only choose the substrings consisting only of 0 characters. Reordering them doesn't change the string at all, so the only string you can obtain is 10010.
5 2
00011
 5 4
11011
 81 5
100000101000000011001101010100001010111000000110000000001000101101111000001000110
 4 3
1011
 47 25
11110011111001110100101010011000110111011011101
 291 159
011001110111110110001111000110001001111100010001011000110100110010001101100110111010101111100111110000110111001100111010001000011001010011011100101000101011010110010011010100100101111010111000001011110101001011101110100100111110011001101010001110110101010101100011101110111000011111011001110
 459 15
101010101010101010101010101010101010101010101111111111111111111111010101010101010101010101011111111111111111111101010101010101010101111111111111111111111101010101010101010111111111111111111111111101010101010101111111111111111111111111110110101010101011111111111111111111111111111001000111111111111111111111111111110000011111111111111111111111111111000001111111111111111111111111111100001111111111111111111111111111100111111111111111111111111111110111111111111
 105 58
110101000111100000011011011101110100001000110011010101100010111001011111010010111101011011010110011011110
 52 11
0110011111001000010000100010010001010100000100110100

10
 5
 187538
 4
 314445058
 1
 0
 132732930
 478323746

#include <iostream>
#include <sstream>
using namespace std;
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <stdio.h>
#include <vector>
#include <iterator>
#include <math.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

// Ordered Set Tree
typedef tree<int, null_type, less_equal<int>,
             rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
#define ll long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fs first
#define ss second
#define loop(i, k, n) for (ll i = k; i < n; i++)
#define tc    \
    ll t;     \
    cin >> t; \
    while (t--)
#define vvpi vector<vector<pair<ll, ll>>>
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
typedef vector<vi> vii;
#define vpi vector<pi>
#define MOD 998244353
#define MAX 10000001
#define dim 200005                                  // CHANGE THIS WHILE SUBMITTING
#define Z 11
#define PRIME 998244353
#define ld long double
#define PI (ld)3.141592653589793
#define all(v) v.begin(),v.end()
#define INF 1000000000000000000

ll pwr(ll a, ll b) {a %= MOD; ll res = 1; while (b > 0) {if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1;} return res;}
ll MOD_mul(ll a, ll b) {a = a % MOD; b = b % MOD; return (((a * b) % MOD) + MOD) % MOD;}

int C[5001][5001];

void binomialCoeff(int n){
    int i, j;
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= n; j++) {
            if (j == 0 || j == i)
                C[i][j] = 1;
            else
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j])%MOD;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    binomialCoeff(5000);
    int n,k; cin>>n>>k;
    string s; cin>>s;
    vi one;
    loop(i,0,n) {
        if(s[i]=='1') one.pb(i);
    }
    vpi p;
    int r=k; int l=-1; int start=0;
    int no_ones = one.size();
    if(k==0 || k > no_ones) {
        cout<<1<<"\n";
        return 0;
    }
    one.pb(n);
    loop(i,0,no_ones-k+1) {
        p.pb({l+1,one[r++]-1});
        l=one[start++];
    }
    for(auto it : p) cout<<it.fs<<" "<<it.ss<<'\n';

    ll ans=0; start=0;
    for(auto it : p) {
        if(!it.fs) { ans=C[it.ss-it.fs+1][k]; start++;}
        else ans = (ans+C[it.ss-it.fs+1][k]-C[one[start+++k-1]-1-it.fs+1][k-1]+MOD)%MOD;
    }
    cout<<ans<<"\n";
}
