给定 $n$ 个点的完全有向图，每个点为黑色或者白色，保证 $1$ 号点为黑色，$2$ 号点为白色。

对于有序点对 $(i,j)(i\not=j)$，存在有向边 $i\to j$，边的颜色由如下规则规定：

• 若 $i<j$ 且 $i,j$ 同色，则边 $i\to j$ 为红色。
• 若 $i<j$ 且 $i,j$ 异色，则边 $i\to j$ 为蓝色。
• 若 $i>j$ 且 $i,j$ 同色，则边 $i\to j$ 为蓝色。
• 若 $i>j$ 且 $i,j$ 异色，则边 $i\to j$ 为红色。

在图中行走时有偏好颜色，初始为蓝色，行走规则如下：

• 若当前位于 $1$ 号节点，将偏好颜色设为蓝色。
• 若当前位于 $2$ 号节点，将偏好颜色设为红色。
• 沿着当前节点一条与偏好颜色一致的出边移动。题目保证一定存在这样的边。
• 重复执行上述流程。

将途经的节点按顺序记为序列 $l_1,l_2,\dots,l_L$。求有多少满足以下条件的合法序列：

• 序列以 $1$ 号节点开头，以 $2$ 号节点结尾。
• $\forall i\in [3,n]$，节点 $i$ 在序列中最多出现一次。
• $\forall j\in [3,L]$，都有 $l_{j-2} \not= l_j$。

数量对 $10^9+7$ 取模。

$3\le n\le 50$。

我们发现只有走到 $1,2$ 时偏好颜色才会改变，所以可以把路径分解成若干非空段 $x\to \cdots\to y(x,y\in \{1,2\})$（中间至少有 $1$ 个 $\in [3,n]$ 的点，我们认为 $1\to 2/2\to 1$ 这种边为段之间的衔接边，例如 $[2\to 3\to 1]\to[2\to 4\to 5\to 2]/[2\to 3\to [1]\to 4\to 5\to 2]$，第二个例子中，我们认为 $1$ 同时在两个段内）。

段只有四种 $1\to 1,1\to 2,2\to 1,2\to 2$，假设分别有 $x_{11},x_{12},x_{21},x_{22}$ 个。

这些段之间可以任意排列，且每种排列补上对应衔接边后方案唯一，因此方案数是 $\frac{(x_{11}+x_{12}+x_{21}+x_{22})!}{x_{11}!x_{12}!x_{21}!x_{22}!}$。

发现段内的偏好颜色相同，而连接段端点的边一个是小编号指向大编号，一个是大编号指向小编号，那么填在两个端点旁的点，一定分别要求和端点同色/异色，因此可以用状态 $(D,S)$ 刻画这个段的内部，即一端要求和点 $D$ 异色，一端要求和点 $S$ 同色。

（发现这样刻画之后，偏好的具体颜色就不重要了，因为当我们在两端填点时已经满足）。

于是 $1\to 1,1\to 2,2\to 1,2\to 2$ 分别对应 $(1,1)/(1,2)/(1,2)/(2,2)$。

然后我们考虑 dp，令 $f_{c_{11},c_{12},c_{21},c_{22}}$ 表示当前还剩 $c_{11}$ 个 $(1,1)$，$c_{1,2}$ 个 $(1,2)$，$c_{2,1}$ 个 $(2,1)$，$c_{2,2}$ 个 $(2,2)$ 时的方案数。

我们依次填入 $3\sim n$，设当前点颜色为点 $t$ 的颜色：

• 可以选择不填，也可以两端都不挨着，将段分裂为两段。

• 当 $D\not=t$ 时可以直接放到异色端点旁边，当 $S=t$ 时可以直接放到同色端点旁边，当 $D\not=t\land S=t$ 时可以同时放两个端点旁边，

系数手推一下是容易的，这里不做展开。

枚举节点 $\mathcal{O}(n)$ 然后状态是 $\mathcal{O}(n^4)$ 的，时间复杂度 $\mathcal{O}(n^5)$。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 50 + 5;
const int mod = 1e9 + 7;

int n;
char s[MAXN];
int fac[MAXN],invf[MAXN];
ll f[MAXN][MAXN][MAXN][MAXN],g[MAXN][MAXN][MAXN][MAXN];

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}

int main(){
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",s+1);
	fac[0]=1;
	FL(i,1,n) fac[i]=1ll*fac[i-1]*i%mod;
	invf[n]=qpow(fac[n],mod-2);
	FR(i,n-1,0) invf[i]=1ll*invf[i+1]*(i+1)%mod;
	FL(c11,0,n-2)
		FL(c12,0,n-2-c11)
			FL(c21,0,n-2-c11-c12)
				FL(c22,0,n-2-c11-c12-c21)
					f[c11][c12+c21][0][c22]+=1ll*fac[c11+c12+c21+c22]*invf[c11]%mod*invf[c12]%mod*invf[c21]%mod*invf[c22]%mod;
	FL(c11,0,n-2)
		FL(c12,0,n-2-c11)
			FL(c21,0,n-2-c11-c12)
				FL(c22,0,n-2-c11-c12-c21)
					f[c11][c12][c21][c22]%=mod;
	FL(i,3,n){
		FL(c11,0,n-2){
			FL(c12,0,n-2-c11){
				FL(c21,0,n-2-c11-c12){
					FL(c22,0,n-2-c11-c12-c21){
						if(!f[c11][c12][c21][c22]) continue;
						ll val=f[c11][c12][c21][c22];
						g[c11][c12][c21][c22]+=f[c11][c12][c21][c22];
						if(s[i]=='B'){
							if(c11)
								g[c11][c12][c21][c22]+=1ll*c11*val%mod,
								g[c11+1][c12][c21][c22]+=1ll*c11*val%mod;
							if(c12)
								g[c11+1][c12][c21][c22]+=1ll*c12*val%mod;
							if(c21)
								g[c11][c12][c21-1][c22]+=1ll*c21*val%mod,
								g[c11+1][c12][c21-1][c22]+=1ll*c21*val%mod,
								g[c11][c12][c21][c22]+=1ll*c21*val%mod,
								g[c11+1][c12][c21][c22]+=1ll*c21*val%mod;
							if(c22)
								g[c11][c12+1][c21][c22-1]+=1ll*c22*val%mod,
								g[c11][c12+1][c21+1][c22-1]+=1ll*c22*val%mod;
						}
						else{
							if(c11)
								g[c11-1][c12][c21+1][c22]+=1ll*c11*val%mod,
								g[c11-1][c12+1][c21+1][c22]+=1ll*c11*val%mod;
							if(c12)
								g[c11][c12-1][c21][c22]+=1ll*c12*val%mod,
								g[c11][c12-1][c21][c22+1]+=1ll*c12*val%mod,
								g[c11][c12][c21][c22]+=1ll*c12*val%mod,
								g[c11][c12][c21][c22+1]+=1ll*c12*val%mod;
							if(c21)
								g[c11][c12][c21][c22+1]+=1ll*c21*val%mod;
							if(c22)
								g[c11][c12][c21][c22]+=1ll*c22*val%mod,
								g[c11][c12][c21][c22+1]+=1ll*c22*val%mod;
						}
					}
				}
			}
		}
		FL(c11,0,n-2)
			FL(c12,0,n-2-c11)
				FL(c21,0,n-2-c11-c12)
					FL(c22,0,n-2-c11-c12-c21)
						f[c11][c12][c21][c22]=g[c11][c12][c21][c22]%mod,g[c11][c12][c21][c22]=0;
	}
	printf("%lld\n",f[0][0][0][0]);
}