注:本题解中下标从1开始
这题可以想出一个(O(n^2))的dp,只要考虑每个偶数位置可以从前面的哪个位置加上一个"B...W..."转移过来
然而数据范围有5e5,,,
打表找规律(误),可以发现转移的时候,能够转移位置构成的集合可能会向前多一个元素,向后多一个元素,或者中间少掉一些或全部元素
简化问题,如果现在在(i)位置有一个W,同时前面的(j)位置到(i)之间没有W,那么在往后转移的过程中,如果转移到了(2i-j),那么(j)就无法向后贡献答案了
就像这样 
可以发现因为(i)位置为W,所以(j)最多只能贡献到位置(2i-j-2)
所以求出每个位置(j)后面最近的W位置(i),然后在(2i-j)处像存图一样跟(j)连边
转移的时候,用一个变量(sum)存储能够转移的所有(f_j)之和,如果当前位置为B就无法转移,否则如果前一个位置为B就只能从这个位置往前两个的位置转移过来,其他情况,用一个指针(tl)表示当前转移区间的左端点,每次往左移动加入答案;还要记得把该位置所连出去的点,也就是无法贡献答案位置贡献扣除,每次把(f_i)加到(sum)里去
这里参考了之前大佬的思路和代码
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define inf 2099999999
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define db double
#define eps (1e-5)
using namespace std;
const int N=500000+10,mod=1000000009;
il LL rd()
{
re LL x=0,w=1;re char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,f[N],nxt[N],tl,sum;
int to[N],nt[N],hd[N],tot=1;
il void add(int x,int y)
{
if(x<=n) ++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;
}
il void del(int x)
{
for(int i=hd[x];i;i=nt[i])
{
if(to[i]>=tl) sum=(sum-f[to[i]]+mod)%mod;
f[to[i]]=0;
}
}
char cc[N];
int main()
{
scanf("%s",cc+1);
n=strlen(cc+1);
if(n&1) {puts("0");return 0;}
nxt[n]=n+1;
for(int i=n-1;i>=0;i--) nxt[i]=(cc[i+1]=='W')?i+1:nxt[i+1];
for(int i=0;i<=n;i+=2) add((nxt[i]<<1)-i,i);
f[0]=sum=1;
for(int i=2;i<=n;i+=2)
{
del(i);
if(cc[i]=='B') sum=0,tl=i;
else if(cc[i-1]=='B') sum=f[i-2],tl=i-2;
else
{
tl-=2;
if(tl>=0) sum=(sum+f[tl])%mod;
}
sum=(sum+(f[i]=sum))%mod;
}
printf("%d
",f[n]);
return 0;
}