满分解法（100 分）

在两个特殊节点处分段

只有节点 $1,2$ 能改变喜欢的颜色，却可以被反复访问；其余节点至多访问一次。直接记录完整行走历史会产生大量重复状态。先将一次行走按每次到达 $1$ 或 $2$ 的位置切开，每段的内部只含普通节点，也可能没有普通节点。

一段从 $1$ 出发时全走蓝边，从 $2$ 出发时全走红边。由题面的染色规则，同一对节点的两个相反方向的边颜色恰好相反。因此把所有红色段反向，所有非空内部段都成为仅由普通节点组成的蓝色有向路径。下面称这样的非空路径为一条“链”，允许只有一个节点。

这些链使用的普通节点互不相交；没有使用的普通节点直接忽略。我们先统计无序的链集合，再恢复它们在原行走中的顺序。

链的首尾颜色决定它的用途

特殊节点的编号都小于普通节点。蓝边从特殊节点进入普通节点时，两端异色；从普通节点回到特殊节点时，两端同色。

以链的首节点颜色、尾节点颜色为类型，得到下表。方向均指已经统一为蓝色的方向。

链类型	补上特殊端点后的蓝色路径	原行走中的用途
$WB$	$1\to\cdots\to1$	在 $1$ 处进行一段蓝色行走
$BW$	$2\to\cdots\to2$	反向使用，在 $2$ 处进行一段红色行走
$WW$	$1\to\cdots\to2$	正向使用，或反向成为从 $2$ 到 $1$ 的红色段
$BB$	$2\to\cdots\to1$	不可作为最终片段

最后一行不能使用：正向需要从 $2$ 走蓝边，反向需要从 $1$ 走红边，两者都与该特殊节点设置的颜色冲突。但构造过程中必须保留 $BB$ 链，因为加入其他普通节点后，它可以变成允许的类型。

从无序链集合恢复行走

设一组链中没有 $BB$ 链，其余三类分别有 $b,c,d$ 条，总数 $k=b+c+d$。

首先给这些链排列顺序，有 $k!$ 种。链由实际的节点编号区分，即使首尾颜色相同，也不是不可区分的对象。每条 $WW$ 链可以选择蓝色正向或红色反向，共有 $2^d$ 种方向选择；另外两类方向固定。

确定这些信息后，行走能否拼接？当前所在的特殊节点与下一条链要求的起点相同时，直接进入链；不同时，先走一条 $1\leftrightarrow2$ 的直接边。$1\to2$ 是蓝边，$2\to1$ 是红边，都符合出发节点设置的颜色。开头从 $1$ 出发，结尾也用同样方式接到 $2$。

每个空隙中的直接边只能这样唯一决定。连续走两条特殊节点之间的边会形成 $1,2,1$ 或 $2,1,2$，题面已经禁止。其他位置也不会产生非法的立即折返：重复的普通节点已被排除；若中间是普通节点，沿同一对端点往返需要两种边颜色，而喜欢的颜色在中间没有改变。

反过来，从任何合法行走中按特殊节点切段，再反转红段，可以唯一恢复链集合、链顺序与各条 $WW$ 链的方向。所以这一对应不重不漏，每个无序链集合的贡献为

$$k!\,2^d.$$

空链集合也有一种行走，即 $1\to2$，与 $0!2^0=1$ 一致。到达 $2$ 后继续走出的合法行走，会由后续链自然计入。

为什么按编号从大到小加入节点

令 $m=N-2$，依次处理普通节点 $N,N-1,\ldots,3$。设刚要加入的节点为 $v$，其颜色为 $t$。已处理的所有节点编号都大于 $v$，于是：

• 旧节点 $u\to v$ 是蓝边，当且仅当 $u$ 与 $v$ 同色。
• $v\to u$ 是蓝边，当且仅当 $u$ 与 $v$ 异色。

因此，新节点能连接哪些链，只取决于链的首尾颜色，不再需要知道端点的具体编号。

定义

$$f(i,a,b,c,d)$$

为处理完最大的 $i$ 个普通节点后，从其中选择任意子集，组成互不相交的非空蓝链，且 $BB,BW,WB,WW$ 四类链的条数恰好分别为 $a,b,c,d$ 的无序链集合数。每条链保留其真实节点和内部顺序，状态只把具有相同四个计数的集合归并。

所有参数非负，且 $a+b+c+d\le i$。初始条件为

$$f(0,0,0,0,0)=1,$$

其他状态为 $0$。所有运算对 $10^9+7$ 取模。

在任一目标链集合中，删除本轮新节点 $v$ 后，只有五种情况：它未被选择；它单独成链；它在链首；它在链尾；它在链内。最后一种情况会把一条链拆成两条不同的链。反过来，插入时分别对应跳过、单独建链、接到链首、接到链尾、连接两条不同的链。删除操作唯一，保证不会按不同构造顺序重复统计同一个集合。

完整转移

以下每行表示

$$f(i+1,\text{目标四元组})\mathrel{+}=f(i,a,b,c,d)\times\text{系数}.$$

新节点是黑色

它可以接在黑色链尾之后，也可以接在白色链首之前。

目标四元组	系数	条件
$(a,b,c,d)$	$1+a+c$	无
$(a+1,b,c,d)$	$1$
$(a+1,b,c-1,d)$	$c$	$c>0$
$(a,b+1,c,d-1)$	$d$	$d>0$
$(a-1,b+1,c,d-1)$	$ad$	$a,d>0$
$(a,b,c-1,d)$	$c(a+c+d-1)$	$c>0$

第一行合并了不选新节点，以及接到某条 $BB$ 或 $WB$ 链尾的情况。第二行是建立单点 $BB$ 链。第三、四行分别把新节点接到 $WB,WW$ 链的首部。第五行把一条 $BB$ 链和一条 $WW$ 链连成 $BW$ 链。

最后一行合并了三类连链：$BB+WB\to BB$、$WB+WB\to WB$、$WB+WW\to WW$。它们都会使 $WB$ 链减少一条，系数分别为 $ac,c(c-1),cd$。中间必须用 $c(c-1)$，因为同一条链不能同时充当左右两条链，否则新节点会把它闭合成环。

新节点是白色

交换上述推导中的黑白颜色，得到：

目标四元组	系数	条件
$(a,b,c,d)$	$1+b+d$	无
$(a,b,c,d+1)$	$1$
$(a,b-1,c,d+1)$	$b$	$b>0$
$(a-1,b,c+1,d)$	$a$	$a>0$
$(a-1,b,c+1,d-1)$	$ad$	$a,d>0$
$(a,b-1,c,d)$	$b(a+b+d-1)$	$b>0$

最后一项同样扣除了将一条 $BW$ 链首尾闭合的 $b$ 种非法选择。每次只从第 $i$ 层更新第 $i+1$ 层，不能让刚加入的节点被再次使用。

答案与小例子

处理完全部普通节点，只允许 $a=0$。根据此前的恢复计数，答案为

$$\boxed{\sum_{\substack{b,c,d\ge0\\b+c+d\le m}} f(m,0,b,c,d)\,(b+c+d)!\,2^d}.$$

预处理 $0!$ 到 $m!$ 及 $2^0$ 到 $2^m$ 即可。

以 BWWB 为例，先处理黑色节点 $4$，可以跳过它，也可以暂时保留单点 $BB$ 链。再处理白色节点 $3$ 时，后者能够通过“接到链首”转移变成 $3\to4$ 的 $WB$ 链。

最终允许的链集合只有三种：空集合，贡献 $1$；只有单点链 $3$，类型为 $WW$，贡献 $2$；只有链 $3\to4$，类型为 $WB$，贡献 $1$。合计 $4$。这个过程也说明，若在中间层直接删除 $BB$ 状态，会丢掉 $1\to3\to4\to1\to2$。

复杂度

时间复杂度为 $O(N^5)$。第 $i$ 层的非负四元组满足总和不超过 $i$，共有 $\binom{i+4}{4}$ 个，每个状态只有常数次转移；所有层总计 $\binom{m+5}{5}$ 个状态。

空间复杂度为 $O(N^5)$。实现保留完整历史层，但只按 $a+b+c+d\le i$ 的合法范围分配各维，不建立五个长度都为 $N$ 的长方体。$N=50$ 时共保存 $\binom{53}{5}=2869685$ 个计数值，阶乘和幂表另占 $O(N)$ 空间。

AC 代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
  int n;
  string s;
  cin >> n >> s;
  constexpr int mod = 1000000007;
  int m = n - 2;
  using layer = vector<vector<vector<vector<int>>>>;
  vector<layer> dp(m + 1);
  for (int i = 0; i <= m; i++) {
    dp[i].resize(i + 1);
    for (int bb = 0; bb <= i; bb++) {
      dp[i][bb].resize(i - bb + 1);
      for (int bw = 0; bb + bw <= i; bw++) {
        dp[i][bb][bw].resize(i - bb - bw + 1);
        for (int wb = 0; bb + bw + wb <= i; wb++) {
          dp[i][bb][bw][wb].resize(i - bb - bw - wb + 1);
        }
      }
    }
  }
  dp[0][0][0][0][0] = 1;
  for (int i = 0; i < m; i++) {
    for (int bb = 0; bb <= i; bb++) {
      for (int bw = 0; bb + bw <= i; bw++) {
        for (int wb = 0; bb + bw + wb <= i; wb++) {
          for (int ww = 0; bb + bw + wb + ww <= i; ww++) {
            int cur = dp[i][bb][bw][wb][ww];
            if (cur == 0) continue;
            auto add = [&](int a, int b, int c, int d, int ways) {
              int& res = dp[i + 1][a][b][c][d];
              res = (res + 1LL * cur * ways) % mod;
            };
            if (s[n - 1 - i] == 'B') {
              add(bb, bw, wb, ww, 1 + bb + wb);
              add(bb + 1, bw, wb, ww, 1);
              if (wb > 0) {
                add(bb + 1, bw, wb - 1, ww, wb);
                add(bb, bw, wb - 1, ww, wb * (bb + wb + ww - 1));
              }
              if (ww > 0) add(bb, bw + 1, wb, ww - 1, ww);
              if (bb > 0 && ww > 0) add(bb - 1, bw + 1, wb, ww - 1, bb * ww);
            } else {
              add(bb, bw, wb, ww, 1 + bw + ww);
              add(bb, bw, wb, ww + 1, 1);
              if (bw > 0) {
                add(bb, bw - 1, wb, ww + 1, bw);
                add(bb, bw - 1, wb, ww, bw * (bb + bw + ww - 1));
              }
              if (bb > 0) add(bb - 1, bw, wb + 1, ww, bb);
              if (bb > 0 && ww > 0) add(bb - 1, bw, wb + 1, ww - 1, bb * ww);
            }
          }
        }
      }
    }
  }
  vector<i64> fact(m + 1, 1), pow2(m + 1, 1);
  for (int i = 1; i <= m; i++) {
    fact[i] = fact[i - 1] * i % mod;
    pow2[i] = pow2[i - 1] * 2 % mod;
  }
  i64 ans = 0;
  for (int bw = 0; bw <= m; bw++) {
    for (int wb = 0; bw + wb <= m; wb++) {
      for (int ww = 0; bw + wb + ww <= m; ww++) {
        ans = (ans + dp[m][0][bw][wb][ww] * fact[bw + wb + ww] % mod * pow2[ww]) % mod;
      }
    }
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}