题意

京电要期末考试啦！！！！！
京电和C电不一样，京电的组合数学考试是电脑上完成的。
老师给你一个01串，你需要所有找出所有的非空子序列使得子序列的前一半都是0，后一半都是1(选择的子序列的长度必须是偶数)。
女神给了你一个眼神，作为老实人，你会帮你的女神做出这题的对吧。
对了，女神希望把最后的结果mod 1e9+7 这样才不用花太多时间去记，有时间和其他男生看电影吃饭呢。

思路

引理1
范德蒙恒等式:
$$\sum_{i=0}^k C_n^i C_m^{k-i}=C_{n+m}^k$$

推论1

$$\begin{align*} \sum_{i=0}^m C_m^i C_n^{i}=C_{n+m}^m \end{align*}$$

其中$m \le n$
推论2

$$\begin{align*} \sum_{i=1}^n C_n^i C_n^{i-1}=C_{2n}^{n-1} \end{align*}$$

证明
对于：

$$\begin{align*} \sum_{i=0}^k C_n^i C_m^{k-i}=C_{n+m}^k \end{align*}$$

令$k=n-1$和$m=n$，则有：

$$\begin{align*} \sum_{i=0}^{n-1} C_n^{i} C_n^{n-i-1}=C_{2n}^{n-1} \end{align*}$$ $$\begin{align*} \therefore \sum_{i=0}^{n-1} C_n^{i+1} C_n^{i}=C_{2n}^{n-1} \end{align*}$$ $$\begin{align*} \therefore \sum_{i=0}^{n} C_n^{i} C_n^{i-1}=C_{2n}^{n-1} \end{align*}$$

推论3

$$\begin{align*} \sum_{i=0}^n (C_n^i)^2 = C_{2n}^n \end{align*}$$

引理2

$$\begin{align*} \because C_{k+1}^i=C_{k}^{i-1}+C_{k}^{i} \end{align*}$$ $$\begin{align*} \therefore C_{k}^{i-1}=C_{k+1}^i-C_{k}^i \end{align*}$$

如果当前这位是0
那么贡献为

$$\begin{align*} \sum_{i=0}^{\min \{a,b-1\}} C_{a}^i C_b^{i+1} \end{align*}$$

其中$a$为前面$0$的个数，$b$为后面$1$的个数（均不包含当前元素）

$$\begin{align*} \sum_{i=0}^{\min \{a,b-1\}} C_{a}^i C_b^{i+1} &= \sum_{i=0}^{\min \{a,b-1\}} (C_{a+1}^{i+1}-C_{a}^{i+1})C_b^{i+1} \\\\ &= \sum_{i=0}^{\min \{a,b-1\}} C_{a+1}^{i+1}C_b^{i+1}-\sum_{i=0}^{\min \{a,b-1\}} C_{a}^{i+1}C_b^{i+1} \\\\ &= \sum_{i=0}^{\min \{a+1,b\}} C_{a+1}^{i}C_b^{i}-\sum_{i=0}^{\min \{a,b\}} C_{a}^{i}C_b^{i} \\\\ &= C_{a+1+b}^{\min \{a+1,b\}}-C_{a+b}^{\min \{a,b\}} \end{align*}$$

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=1e6+7;
typedef long long ll;
const ll mod=1e9+7LL;
char s[Nmax];
int zero_sum[Nmax];
int one_sum[Nmax];
ll qmod(ll base,ll n)
{
    ll ans=1LL;
    base%=mod;
    while(n>0)
    {
        if(n&1)
            ans=(ans*base)%mod;
        base=(base*base)%mod;
        n>>=1;
    }
    return ans;
}
ll fac[Nmax],inv[Nmax];
ll C(ll n,ll m)
{
    ll ans;
    if(m>n)
        return 0LL;
    if(n<=0)
        return 0LL;
    if(m<0)
        return 0LL;
    if(m==0 || n==m )
        return 1;
    ans=fac[n];
    ans=ans*inv[m]%mod;
    ans=ans*inv[n-m]%mod;
    return ans;
}
int main()
{
    #ifdef test
    #endif
    //freopen("a.in","r",stdin);
    fac[0]=1LL;
    for(int i=1;i<=200000;i++)
    {
        fac[i]=i*fac[i-1]%mod;
        inv[i]=qmod(fac[i],mod-2LL);
    }
    //printf("fac[%d]:%lld\n",5,fac[5]);
    scanf("%s",s+1); 
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)
    {
        zero_sum[i]=zero_sum[i-1];
        one_sum[i]=one_sum[i-1];
        if(s[i]=='0')
            zero_sum[i]++;
        else
            one_sum[i]++;
    }
    int a,b,m;
    ll ans=0LL;
    for(int i=1;i<=n;i++)
    {
        a=zero_sum[i-1];
        b=one_sum[n]-one_sum[i-1];
        m=min(a+1,b);
        int mm=(a,b);
        if(s[i]=='0')
        {
            ans=(ans+C(a+b+1,m))%mod;
            ans=(ans-C(a+b,mm))%mod;
            if(ans<0)
                ans+=mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}