白黑两段中的路径块配对（通过子任务 3–4，共 32 分）

适用于子任务 $3,4$。除了黑色节点 $1$，其余节点按编号先是一个白色段，再是一个可能为空的黑色段。令普通白点数为 $w$，普通黑点数为 $b$，两者都不包括特殊节点。

一条路径中可以有哪些颜色段

在特殊节点 $1,2$ 处分段，将从 $2$ 出发的红段反转。由于一对节点的相反方向的边颜色相反，每段内部成为普通节点上的蓝色链。

同色节点间的蓝边按编号递减。任意白色普通节点的编号小于任意黑色普通节点，异色蓝边只能从白色到黑色。因此一条蓝链只能是白链、黑链，或一段递减白链后接一段递减黑链。

纯黑链不能单独用于原行走：补上特殊端点后蓝色方向为 $2\to\cdots\to1$，但 $2$ 处喜欢红色；反向又会从 $1$ 走红边，同样不允许。纯白链可正向从 $1$ 走到 $2$，或反向从 $2$ 走到 $1$。白链接黑链则只能正向作为 $1\to\cdots\to1$ 的蓝段。

于是，先把选出的白点划成 $k$ 个非空块，黑点划成 $r$ 个非空块，各块内部按编号递减。每个黑块必须接到一个白块的末尾，且不同黑块不能使用同一个白块。反过来，任何这样的配对都产生合法的互不相交蓝链。

分块数与配对数

定义 $f(t,j)$ 为从 $t$ 个有标号节点中选择一个子集，并划分成恰好 $j$ 个无序非空块的方案数。初始化 $f(0,0)=1$，其余为零。对于 $0\le j\le t<w+b$：

$$\begin{aligned} f(t+1,j)&\mathrel{+}=(j+1)f(t,j),\\ f(t+1,j+1)&\mathrel{+}=f(t,j). \end{aligned}$$

第一项来自不选择新点，或加入一个已有块；第二项是让新点单独成块。白点与黑点分别查询同一张表的 $f(w,k)$ 和 $f(b,r)$。

给 $r$ 个黑块分配互不相同的白块，有

$$P(k,r)=k(k-1)\cdots(k-r+1),\qquad P(k,0)=1$$

种方式，要求 $0\le r\le k$。虽然分块时不对块排序，每个黑块仍由其实际节点集合区分，所以这里需要计数有标号黑块的注入映射。

配对后仍有 $k$ 条链，其中 $r$ 条是白黑混合链，只有一种方向；另外 $k-r$ 条为纯白链，各有两种方向。将全部链排列有 $k!$ 种，再按特殊端点补零条或一条直接边，补法唯一。不能在空隙补两条直接边，因为那会立即折返。

因此答案为

$$\sum_{k=0}^{w}\sum_{r=0}^{\min(k,b)} f(w,k)f(b,r)P(k,r)2^{k-r}k! \pmod{10^9+7}.$$

$k=r=0$ 对应行走 $1\to2$。没有黑色普通节点时，只有 $r=0$，自动覆盖子任务 $3$；没有白色普通节点时，只能取 $k=r=0$，答案为 $1$。

预处理阶乘和二次幂。固定 $k$ 后，下降积从 $P(k,0)=1$ 开始，每次乘 $k-r$ 即得到下一项，不需要模逆元。

时间复杂度为 $O(N^2)$，空间复杂度为 $O(N^2)$，包括完整分块表。该方法使用了白点编号全部小于黑点的条件，不能把任意输入按颜色重新排列后套用公式；某些其他排列恰好有相同答案，也不代表公式适用于一般交错排列。

参考代码（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;
  int white = 0;
  for (int i = 2; i < n; i++) white += (s[i] == 'W');
  int black = m - white;
  vector<vector<int>> dp(m + 1, vector<int>(m + 1));
  dp[0][0] = 1;
  for (int i = 0; i < m; i++) {
    for (int k = 0; k <= i; k++) {
      dp[i + 1][k] = (dp[i + 1][k] + 1LL * (k + 1) * dp[i][k]) % mod;
      dp[i + 1][k + 1] = (dp[i + 1][k + 1] + dp[i][k]) % mod;
    }
  }
  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 k = 0; k <= white; k++) {
    i64 prod = 1;
    for (int r = 0; r <= min(k, black); r++) {
      i64 cur = 1LL * dp[white][k] * dp[black][r] % mod;
      cur = cur * prod % mod * pow2[k - r] % mod * fact[k] % mod;
      ans = (ans + cur) % mod;
      prod = prod * (k - r) % mod;
    }
  }
  cout << ans << '\n';
}

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