#include using namespace std; const int MAX_N=1<<21|5,MOD=1e9+7; int d[MAX_N],f[MAX_N],dl[MAX_N],g[MAX_N]; vector key; char s[MAX_N]; void mo(int& x) { x>=MOD?x-=MOD:0; } void cdq(int l,int r){ if(l==r){ if(s[d[l]]=='+') f[l]=0; g[l]=f[l]; // printf("<%d %d>",l,f[l]); return; } // printf("[%d %d]",l,r); int mid=l+r>>1; cdq(l,mid); // printf("[%d %d %d]",l,mid,r); for(int i=l,j=mid+1;i<=mid;++i,++j) mo(f[j]+=g[i]); // for(int i=l;i<=r;++i) printf("{%d %d %d}",i,f[i],g[i]); puts(""); cdq(mid+1,r); for(int i=l,j=mid+1;i<=mid;++i,++j) mo(g[j]+=g[i]); } int main(){ for(int i=0;i<=21;++i) dl[1<