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<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> pbds_mset;
typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> pbds_set;
template<typename T> // cin >> vector<T>
istream& operator>>(istream &istream, vector<T> &v) { for (auto &it : v) cin >> it; return istream; }
template<typename T> // cout << vector<T>
ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }
#define ll long long
#define pb push_back
#define f first
#define s second
#define mod 1000000007
#define mod2 998244353
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pair<ll,ll>>
#define pqmax priority_queue<ll>
#define pqmin priority_queue<ll,vll,greater<ll>>
#define val_at find_by_order
//*st.find_by_order(n)
#define less_than order_of_key
//st.order_of_key(n)

ll power(ll x,ll y, ll p)
{
    ll res = 1;

    x = x % p;


    while (y > 0)
    {


        if (y & 1)
            res = (res * x) % p;


        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

ll modInverse(ll n, ll p)
{
    return power(n, p - 2, p);
}

ll nCr(ll n,ll r, ll p=mod2)
{
    if (n < r)
        return 0;
    if (r == 0)
        return 1;

   ll fac[n + 1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;

    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
           % p;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t;
	t=1;
	//cin>>t;
	start:
	while(t--){

            ll n,k;
    cin>>n>>k;
    string s;
    cin>>s;

    if(k==0){
        cout<<"1"<<endl;
        goto start;
    }

    ll sum=0,st=-1;

    for(ll i=0;i<s.size();i++){
        sum+=(s[i]-'0');
        if(sum>k){
            st=i;
            break;
        }
    }

    if(st==-1 && sum<k){
        cout<<"1"<<endl;
        goto start;
    }

    ll ans=nCr(st,k),len=st;

    for(ll i=st;i<n;i++){
        if(s[i]=='0'){
            len++;
            ans=(ans+nCr(len-1,k-1))%mod2;
        }
        else ans=(ans+nCr(len-1,k))%mod2;
        ans=ans%mod2;
    }

    cout<<ans%mod2<<endl;



	}
	return 0;

}
