每天来一段宇宙语，心情舒畅，压力全消。阿啦啦哭喽，哭喽得给给候弄哭来，嗨那来开赛地哭喽哈嘛呢那你哭来赛地候呢不来太太那赛地的扣

· · 题解

这我能做？

首先肯定不能在原序列上做不然谁做谁完蛋。

只有 0/1，我们来看看操作。首先左边有 0 的 1 一定可以被删除（哦耶，以及 0 与 0 的相对位置不变，1 与 1 的相对位置不变。如果被删除了可以看作删了最前面的然后后面整体平移！我们把 0 看成板，1 看成球，那么操作 2 就是 1 向前挪一个格子，操作 1 就是挪到最前面！设挪动的最大步数为 b_i（即右边的 0 的个数 +1），实际走的步数为 w_i，那么约束有：w_{i-1}\le w_i\le w_{i+1},0\le w_i \le b_i。

设 f_{i,j} 为第 i 个 1 前面有 j 个板，显然的有 f_{0,0}=1，那么有 f_{i,j}=\sum_{k=0}^{j}f_{i-1,k}，前缀和优化即可。

#include<bits/stdc++.h>

#define int ll
#define pii pair<int,int> 
#define pll pair<long long,long long> 
#define ll long long
#define i128 __int128

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define in4(a,b,c,d) a=read(), b=read(), c=read(), d=read()
#define dbg puts("IAKIOI")
#define rtn(x) return cout<<(x)<<'\n',void();

using namespace std;

int read() {
    int x=0,f=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
    for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }

const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int qpo(int a,int b,const int mod) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }
int inv(int a,const int mod) {return qpo(a,mod-2,mod); }

const int maxn = 100050;

int n,a[maxn],b[maxn];

int f[2][maxn],s[2][maxn];

void work() {
    in1(n); int m=0; int flg=0;
    For(i,1,n) {
        char ch=getchar(); while(ch!='0'&&ch!='1') ch=getchar();
        a[i]=ch-'0'; if(a[i]==0&&flg==0) flg=i; 
        if(a[i]==1&&flg!=0) m++,b[m]=i-m-flg+2;
    }
    For(i,0,n) f[0][i]=f[1][i]=0,s[0][i]=s[1][i]=0;
    f[0][0]=1; s[0][0]=1; For(i,1,n) s[0][i]=1;
//  For(i,1,m) cout<<b[i]<<' '; cout<<'\n';
    For(i,1,m) {
        int p=i&1; int q=p^1;
        For(j,0,n) f[p][j]=0,s[p][j]=0; 
        For(j,0,b[i]) {
            f[p][j]=s[q][j]; 
            if(j>0) s[p][j]=(s[p][j-1]+f[p][j])%mod;
            else s[p][j]=f[p][j];
        }
        For(j,b[i]+1,n) s[p][j]=s[p][j-1];
    }
    int ans=0;
    For(i,0,n) ans=(ans+f[m&1][i])%mod; cout<<ans<<'\n';
}

signed main() {
//  freopen("data.in","r",stdin);
//  freopen("myans.out","w",stdout);
//  ios::sync_with_stdio(false); 
//  cin.tie(0); cout.tie(0);
    double stt=clock();
    int _=1;
    _=read();
//  cin>>_;
    For(i,1,_) {
        work();
    }
    cerr<<"\nTotal Time is:"<<(clock()-stt)*1.0/1000<<" second(s)."<<'\n';
    return 0;
}