LINK：小V和字符串
容易想到只有1个数相同的 才能有贡献。
知道两个01串 那么容易得到最小步数 大体上就是 第一个串的最前的1和第二个串最前的1进行匹配。
容易想到设f[i][j]表示 前i位1的个数为j的贡献.
不过在 j-1 向 j进行转移的时候 两个集合的贡献无法得到 因为我们只知道其中一个串的最后一个1的位置。
考虑如果每次合并集合时 只统计最后一个1的贡献 那么这样无论怎么做都是错误的。
回到先前 还是考虑描绘出两个串长什么样子 然后 考虑如何统计答案。
问题变成了 逐位考虑 统计两个串的贡献。
那么先前那个匹配的工程就变成了对于每个前缀 1的数量是否相等 不相等 其中一个串的1要整体向右移动 不断进行这样的匹配即可。
这样我们就可以逐位得到贡献 累计上方案数就可以得到答案了。
值得一提的是 要记录其1的差值 下标为负可以进行调整。
由于两个串的贡献都会被统计两次 所以要除以2.
const int MAXN=1010,INV=(1+mod)>>1;
int n,m,maxx;
char a[MAXN];
int f[MAXN][MAXN][2][2];//方案数
int g[MAXN][MAXN][2][2];//答案
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int mus(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return (ll)x*y%mod;}
int main()
{
freopen("1.in","r",stdin);
gc(a);n=strlen(a+1);
f[0][502][1][1]=1;m=n>>1;
rep(1,n,i)
{
rep(max(-i,-m),min(i,m),j)
{
int cc=j+502;
rep(0,1,l)
rep(0,1,r)
{
int w1=l==1?a[i]-'0':1;
int w2=r==1?a[i]-'0':1;
//两者都为0
f[i][cc][l==1&&w1==0][r==1&&w2==0]=add(f[i][cc][l==1&&w1==0][r==1&&w2==0],f[i-1][cc][l][r]);
g[i][cc][l==1&&w1==0][r==1&&w2==0]=add(g[i][cc][l==1&&w1==0][r==1&&w2==0],add(g[i-1][cc][l][r],mul(f[i-1][cc][l][r],abs(j))));
//两者都为1
if(w1&&w2)
{
f[i][cc][l==1&&w1==1][r==1&&w2==1]=add(f[i][cc][l==1&&w1==1][r==1&&w2==1],f[i-1][cc][l][r]);
g[i][cc][l==1&&w1==1][r==1&&w2==1]=add(g[i][cc][l==1&&w1==1][r==1&&w2==1],add(g[i-1][cc][l][r],mul(f[i-1][cc][l][r],abs(j))));
}
//第一个串为1.
if(w1)
{
f[i][cc+1][l==1&&w1==1][r==1&&w2==0]=add(f[i][cc+1][l==1&&w1==1][r==1&&w2==0],f[i-1][cc][l][r]);
g[i][cc+1][l==1&&w1==1][r==1&&w2==0]=add(g[i][cc+1][l==1&&w1==1][r==1&&w2==0],add(g[i-1][cc][l][r],mul(f[i-1][cc][l][r],abs(j+1))));
}
if(w2)
{
f[i][cc-1][l==1&&w1==0][r==1&&w2==1]=add(f[i][cc-1][l==1&&w1==0][r==1&&w2==1],f[i-1][cc][l][r]);
g[i][cc-1][l==1&&w1==0][r==1&&w2==1]=add(g[i][cc-1][l==1&&w1==0][r==1&&w2==1],add(g[i-1][cc][l][r],mul(f[i-1][cc][l][r],abs(j-1))));
}
}
}
}
put(mul(INV,add(add(g[n][502][0][0],g[n][502][0][1]),add(g[n][502][1][0],g[n][502][1][1]))));
return 0;
}