题意:给你n个01字符,每次问你前缀的所有本质不同的子串,由摩斯密码组成的方案数和.

题解:离线处理,把字符建sam,通过topo序来dp计算每个节点表示的子串方案数的和.统计答案时,把n个字符挨个匹配过去,把所有经过的节点加上方案数,还有每个节点的fa链,也要统计(因为是当前串的后缀),用一个vis标记访问过没有.复杂度O(n*32),于是这题n能出到1e6

//#pragma GCC optimize(2)

//#pragma GCC optimize(3)

//#pragma GCC optimize(4)

//#pragma GCC optimize("unroll-loops")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>

#define fi first

#define se second

#define db double

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define ld long double

//#define C 0.5772156649

//#define ls l,m,rt<<1

//#define rs m+1,r,rt<<1|1

#define pll pair<ll,ll>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define ull unsigned long long

//#define base 1000000000000000000

#define fin freopen("a.txt","r",stdin)

#define fout freopen("a.txt","w",stdout)

#define fio ios::sync_with_stdio(false);cin.tie(0)

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}

inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}

template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}

template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}

inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}

inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}

using namespace std;

const ull ba=233;

const db eps=1e-7;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=3000+10,maxn=100000+10,inf=0x3f3f3f3f;

int n,b[N];

char s[N];

struct SAM{

    int last,cnt;

    int ch[N<<1][2],fa[N<<1],l[N<<1];

    int a[N<<1],c[N<<1];

    bool vis[N<<1];

    ll dp[N<<1];

    void ins(int c,int id){

        int p=last,np=++cnt;last=np;l[np]=l[p]+1;

        for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;

        if(!p)fa[np]=1;

        else

        {

            int q=ch[p][c];

            if(l[p]+1==l[q])fa[np]=q;

            else

            {

                int nq=++cnt;l[nq]=l[p]+1;

                memcpy(ch[nq],ch[q],sizeof(ch[q]));

                fa[nq]=fa[q];fa[q]=fa[np]=nq;

                for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;

            }

        }

    }

    void topo()

    {

        for(int i=1;i<=cnt;i++)c[l[i]]++;

        for(int i=1;i<=cnt;i++)c[i]+=c[i-1];

        for(int i=1;i<=cnt;i++)a[c[l[i]]--]=i;

    }

    void build(){

        last=cnt=1;

        dp[1]=1;

    }

    void dfs(int u,int dep,ll x,int now)

    {

        if(dep==0&&(now==3||now==5||now==14||now==15));

        else if(dep!=4)add(dp[u],x);

        if(dep==0)return ;

        for(int i=0;i<2;i++)if(ch[u][i])

            dfs(ch[u][i],dep-1,x,now*2+i);

    }

    void cal()

    {

        topo();

        for(int i=1;i<=cnt;i++)dfs(a[i],4,dp[a[i]],0);

        int now=1;ll ans=0;

        vis[1]=1;

        for(int i=1;i<=n;i++)

        {

            now=ch[now][b[i]];

            add(ans,dp[now]);vis[now]=1;

            int te=fa[now];

            while(te&&!vis[te])

            {

                vis[te]=1,add(ans,dp[te]);

                te=fa[te];

            }

            printf("%lld\n",ans);

        }

    }

}sam;

int main()

{

    scanf("%d",&n);

    sam.build();

    for(int i=1,x;i<=n;i++)scanf("%d",&b[i]),sam.ins(b[i],i);

    sam.cal();

    return 0;

}

/********************

********************/