在这个科技发达的年代，真人表演已经落伍了。参加完 UOI 后，hehe 蚤去到了下山市大剧院，观看下山市最火爆的机器人表演。
机器人有时比人类更能抓住事情的本质。所谓表演，其实也就是开场有若干个机器人，中间有时一些机器人出现，有时一些机器人消失，最后谢幕还剩若干个机器人的过程。
hehe 蚤得到了一份公开的节目单。这份节目单介绍了按照时间顺序的一些事件。事件共有两种，一种是“某个机器人出现在了舞台上”，另一种是“某个机器人从舞台上消失了”。
但节目单上没有记录开场时会有多少个机器人，也没有记录谢幕时会有多少个机器人。
除此之外，还有 $t$ 个临时安排的机器人会来这次表演。hehe 蚤并不知道他们何时会来，何时会消失（但它们一定会来也一定会消失）。
hehe 蚤决定按照时间顺序记录整个表演。他会用 0 表示一个机器人出现在舞台上，用 1 表示一个机器人从舞台上消失，如此形成一个 01 串。
在表演开始前，hehe 蚤想知道最终 01 串共有多少种可能性。答案对 $998244353$ 取模。
简要题意：
有一个长为 $n$ 的 01 串，你需要计算 $t$ 次操作后能得到多少不同的 01 串。
一次操作的定义为：在串中选两个位置插入一对 01 使得 0 在 1 前。
对于所有数据，保证 $1 \leq n, t \leq 300$。
dp 题，先考虑如何判定一个串是否可以操作出来。
贪心的话，考虑能去匹配原串的就去匹配原串，不能匹配的就去凑 01.记一下现在前面有多少个 0 没有匹配。
然后发现如果前面没有 0 不能匹配了，但是又有一个 1 要去匹配，这个时候我们只能撤回那些拿去匹配原串的字符，找一个最大的 \(i\) 使得撤回原串中 \(i\) 后面的所有 01 后，有多的 0 可以拿来匹配这个 1.这个可以暴力去找。
然后考虑把上面反悔贪心的过程记到 dp 里面。定义 \(dp_{i,j,k}\) 为前 \(i\) 个数，和原串匹配了 \(j\) 位，有 \(k\) 个 0 没有匹配 1，然后按着上面的反悔贪心去转移就可以了。
#include<bits/stdc++.h>
using namespace std;
const int N=305,P=998244353;
int f[N],h[N],n,t,dp[N*3][N][N];//dp[i][j][k] 表示现在到了i，匹配到j,前面有k个0
char s[N];
int main()
{
scanf("%d%d%s",&n,&t,s+1);
for(int i=n;i;i--)
{
int c=0;
for(int j=i;j<=n;j++)
{
if(s[j]=='0')
++c;
else
--c;
if(c<0)
break;
if(!f[j]&&c)
f[j]=i,h[j]=c;
}
}
dp[0][0][0]=1;
for(int i=0;i<n+2*t;i++)
{
for(int j=0;j<=n;j++)
{
for(int k=0;k<=t;k++)
{
if(j^n)
{
(dp[i+1][j+1][k]+=dp[i][j][k])%=P;
if(s[j+1]=='0')
{
if(k)
(dp[i+1][j][k-1]+=dp[i][j][k])%=P;
else if(f[j])
(dp[i+1][f[j]-1][h[j]-1]+=dp[i][j][k])%=P;
}
else
(dp[i+1][j][k+1]+=dp[i][j][k])%=P;
}
else
{
(dp[i+1][j][k+1]+=dp[i][j][k])%=P;
if(k)
(dp[i+1][j][k-1]+=dp[i][j][k])%=P;
else if(f[j])
(dp[i+1][f[j]-1][h[j]-1]+=dp[i][j][k])%=P;
}
}
}
}
printf("%d",dp[n+2*t][n][0]);
}