Give you two strings S and t consisting of numbers (character'0'SIM' 9'). The length of S is n, and the length of T is m. The first character of S and t is not'0'. If considered a positive integer, count the number of valid subsequences of s greater than t. The subsequence is valid only if and only if its first character is not "0". If two subsequences consist of different positions in the original string, they are different. For example, the string "1223" has two distinct subsequences "23". Because the answer may be very large, please output the answer of modulus 998244353.

Thought: In fact, only need to consider the number of the same length (m) as the second string, the length greater than the number of combinations can be quickly calculated. We use dp[i][j] to denote that the i-th bit I s the j-th bit in the s-string, so dp[i][j] = sum (dp [i-1] [k]) (i-1 <= K < j), prefix and one-dimensional optimization can be achieved. But there will be a bigger one before, and the latter will not have to be bigger to satisfy, so we need to record this situation, using the g array to record how many cases are bigger than before, and then we can transfer. The code is written on the court, which is ugly.

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e3+7;
const int mod=998244353;
char s[maxn],t[maxn];
int d[maxn][maxn];
int g[maxn][maxn];
ll sum[maxn][maxn];
ll sum1[maxn][maxn];
 
ll a[maxn],b[maxn];//a[i] is the factorial of I and b[i] is the inverse division element of the factorial. Both of them are used to calculate the number of combinations.
ll qpow(ll n,ll k,ll mod){
    ll res=1;
    n=n%mod;
    while(k){
        if(k&1)res=res*n%mod;
        n=n*n%mod;
        k>>=1;
    }
    return res;
}
void init(){
    a[0]=b[0]=1;
    for(int i=1;i<maxn;++i){
        a[i]=(a[i-1]*i)%mod;
    }
    b[maxn-1]=qpow(a[maxn-1],mod-2,mod);        //maxn-1 must be less than mod
    for(int i=maxn-1;i>0;i--)
        b[i-1]=b[i]*i%mod;
}
ll C(ll n,ll m){
    if(n<m)return 0;
    return  a[n]*b[m]%mod*b[n-m]%mod;
}
 
int main(){
    int t1;
    init();
    scanf("%d",&t1);
    while(t1--){
 
        int n,m;
        scanf("%d%d",&n,&m);
        scanf(" %s",s+1);
        scanf(" %s",t+1);
        ll tmp = 0;
        for(ll i = m + 1; i <= n; ++i)
        {
            for(ll j = 1; j + i - 1 <= n; ++j)
            {
                if(s[j] != '0')
                    tmp = (tmp + C(n - j, i - 1)) % mod;
            }
        }
        ll ans = 0;
        if(m==1){
            for(int i=1;i<=n;i++)
                if(s[i]>t[1])
                ans++;
            ans = (ans + tmp) % mod;
            printf("%lld\n", ans);
 
            for(int i=0;i<=n;i++){
                for(int j=0;j<=n;j++)d[i][j]=g[i][j]=sum[i][j]=sum1[i][j]=0;
            }
                continue;
 
        }
        for(int i=1;i<=n;i++)
        {
            if(s[i]>t[1])
            {
                d[1][i]=1;
                g[1][i]=1;
 
            }
            else if(s[i] == t[1])
                d[1][i] = 1;
            sum[1][i]=(sum[1][i-1]+d[1][i]) % mod;
            sum1[1][i]=(sum1[1][i-1]+g[1][i]) % mod;
 
        }
        for(int i = 2; i <= m; i++){
            for(int j = i; j <= n; j++){
 
                    if(s[j] < t[i] || ((i == m) && (s[j] == t[i]))) //Less than or equal to the last bit.
                    {
 
                        d[i][j] = (d[i][j] + sum1[i-1][j-1]-sum1[i-1][i-2] + mod) % mod;
                        g[i][j] = (g[i][j] + sum1[i-1][j-1]-sum1[i-1][i-2] + mod) % mod;
 
                        sum[i][j]=(d[i][j]+sum[i][j-1]) % mod;
                        sum1[i][j]=(g[i][j]+sum1[i][j-1]) % mod;
 
                    }
                    else  //The case of greater than
                    {
 
                        d[i][j] = (d[i][j] + sum[i-1][j-1]-sum[i-1][i-2] + mod) % mod;
                        if(s[j] == t[i]) //Equal
                            g[i][j] =(g[i][j] + sum1[i-1][j-1]-sum1[i-1][i-2] + mod) % mod;
                        else
                            g[i][j] = (g[i][j] + sum[i-1][j-1]-sum[i-1][i-2] + mod) % mod;
                        sum[i][j]=(d[i][j]+sum[i][j-1]) % mod;
                        sum1[i][j]=(g[i][j]+sum1[i][j-1]) % mod;
 
                    }
                }
            }
 
 
        for(int i = m; i <= n; ++i)
            ans = (ans + d[m][i]) % mod;
        ans = (ans + tmp) % mod;
        printf("%lld\n", ans);
                    for(int i=0;i<=n;i++){
                for(int j=0;j<=n;j++)d[i][j]=g[i][j]=sum[i][j]=sum1[i][j]=0;
            }
    }
 
    return 0;
}