满分解法（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();
}

白黑两段中的路径块配对（通过子任务 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();
}

只有一个黑点时的分块计数（通过子任务 3，共 16 分）

适用于子任务 $3$：只有节点 $1$ 为黑色，其余节点全部为白色。令 $m=N-2$ 为普通节点数。

普通节点段变为单调块

在每次到达 $1$ 或 $2$ 的位置切开行走。一段从 $1$ 出发走蓝边，从 $2$ 出发走红边。同一对节点的反向边颜色相反，因此把红段反转，段内就统一为蓝边。

普通节点全部同色，蓝边只从较大编号指向较小编号。于是，每个非空普通节点段恰好是一个节点集合按编号递减排列得到的链。链首尾都是白色，正向补上特殊端点是 $1\to\cdots\to2$，也可以反向作为 $2\to\cdots\to1$ 的红段。

若选出的普通节点分成 $k$ 个非空块，每块的内部顺序已经唯一确定。各块按实际节点区分，有 $k!$ 种排列，每块又有两种使用方向。相邻块的特殊端点不同时补一条直接边，相同时不补；开头从 $1$ 接入，结尾接到 $2$，这些连接都唯一。两个连续直接边会立即折返，所以不存在其他补法。

因此每个无序分块贡献 $k!2^k$ 种行走。

选择子集并分块

定义 $f(i,k)$ 为从 $i$ 个已处理的普通节点中选择任意子集，并将所选节点划分为恰好 $k$ 个无序非空块的方案数。初始

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

其余状态为零。对 $0\le k\le i<m$，新节点有三种去向：不选、加入已有的 $k$ 个块之一、单独建立新块。所以

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

每个已有块是实际节点集合，加入不同块会产生不同划分。删除新节点可唯一确定它来自“不选、旧块或新块”，因此没有重计。

答案为

$$\sum_{k=0}^{m}f(m,k)k!2^k\pmod{10^9+7}.$$

其中 $k=0$ 对应空普通节点集合，即 $1\to2$。代码从系数 $1$ 开始，每次乘 $2(k+1)$，依次得到所需的 $k!2^k$。

时间复杂度为 $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;
  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;
    }
  }
  i64 ans = 0, coef = 1;
  for (int k = 0; k <= m; k++) {
    ans = (ans + dp[m][k] * coef) % mod;
    coef = coef * 2 * (k + 1) % mod;
  }
  cout << ans << '\n';
}

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

压缩特殊节点后的子集动态规划（通过子任务 1–2，共 16 分）

适用于子任务 $1,2$，即 $N\le20$。只给普通节点 $3,\ldots,N$ 编号到一个集合中，令其数量为 $m=N-2$。

压缩特殊节点之间的移动

从一个普通节点出发，在喜欢的颜色固定时，通向 $1,2$ 的两条边颜色相反，所以恰有一个特殊节点可以直接到达。到达后，可以立即离开，也可以再经过另一个特殊节点；不能再走第三个特殊节点，否则立即折返。

从 $1$ 出发只能沿蓝边进入白色普通节点，从 $2$ 出发只能沿红边进入白色普通节点。因此，从任意一个普通节点状态出发，经一个或两个特殊节点到达下一个白色普通节点，有且仅有两种方式：最后从 $1$ 进入，颜色为蓝；或者最后从 $2$ 进入，颜色为红。

同样，从任一普通节点状态到达 $2$ 并结束，有且仅有一种不再访问普通节点的方式：若可直接到达的是 $2$ 就停止，否则先到 $1$ 再到 $2$。起始阶段也有两种进入第一个白色普通节点的方式，即从 $1$ 直接进入，或先到 $2$ 再进入。

这些压缩不会引入立即折返。下一普通节点必须尚未访问；在普通节点处反向走刚才的边又需要相反颜色，而普通节点不改变颜色；特殊节点之间则明确只允许走一条直接边。

集合状态与转移

定义 $f(S,u,c)$ 为已访问普通节点集合恰为 $S$、当前位置是 $u\in S$、喜欢颜色为 $c$ 的合法前缀数量。两个颜色都保留，空集合没有普通节点结尾，初始所有 $f$ 为零。

令

$$g(S)=[S=\varnothing]+\sum_{u\in S}\sum_{c\in\{\text{红},\text{蓝}\}}f(S,u,c).$$

其中 $g(\varnothing)=1$ 代表从 $1$ 开始、还没有访问普通节点的初始状态。

对每个尚未访问的普通节点 $v\notin S$，分两类更新。

若 $v$ 为白色，则通过特殊节点进入 $v$ 的转移为

$$\begin{aligned} f(S\cup\{v\},v,\text{蓝})&\mathrel{+}=g(S),\\ f(S\cup\{v\},v,\text{红})&\mathrel{+}=g(S). \end{aligned}$$

另外，对于 $u\in S$，若 $u\to v$ 为颜色 $c$ 的边，可以直接移动而不改变颜色：

$$f(S\cup\{v\},v,c)\mathrel{+}=f(S,u,c).$$

直接移动与经过特殊节点的移动对应不同节点序列，应分别累加。每次转移都会增加一个普通节点，按集合掩码递增计算即可。

最终答案为

$$\sum_{S\subseteq\{3,\ldots,N\}}g(S).$$

非空集合的每个前缀都有唯一的“到 $2$ 后结束”方式；空集合贡献直接行走 $1\to2$。每条完整行走由最后一个普通节点及其前缀唯一确定，所以该求和没有重计。所有运算对 $10^9+7$ 取模。

时间复杂度为 $O(m^2 2^m)$，每个集合枚举前后两个普通节点；空间复杂度为 $O(m2^m)$，保留完整的集合、末端节点、颜色三维表。$m\le18$ 时可行，较大的 $N$ 会使指数空间超过限制。

参考代码（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;
  i64 count = 1LL << m;
  vector<vector<vector<int>>> dp(count, vector<vector<int>>(m, vector<int>(2)));
  int ans = 0;
  auto add = [&](int& res, int value) {
    res += value;
    if (res >= mod) res -= mod;
  };
  for (i64 mask = 0; mask < count; mask++) {
    int sum = (mask == 0);
    for (int u = 0; u < m; u++) {
      for (int value : dp[mask][u]) add(sum, value);
    }
    add(ans, sum);
    for (int v = 0; v < m; v++) {
      if (mask >> v & 1) continue;
      i64 nxt = mask | (1LL << v);
      if (s[v + 2] == 'W') {
        add(dp[nxt][v][0], sum);
        add(dp[nxt][v][1], sum);
      }
      for (int u = 0; u < m; u++) {
        if (!(mask >> u & 1)) continue;
        int blue = (u < v) != (s[u + 2] == s[v + 2]);
        add(dp[nxt][v][blue], dp[mask][u][blue]);
      }
    }
  }
  cout << ans << '\n';
}

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

按原规则枚举行走（通过子任务 1，共 4 分）

适用于子任务 $1$，即 $N\le8$。

维护已经访问的普通节点集合 $S$、当前节点 $u$、前一个节点 $p$ 和当前喜欢的颜色 $c$，直接按题目规则搜索下一步。到达 $1$ 时将颜色设为蓝色，到达 $2$ 时设为红色。

定义 $F(S,u,p,c)$ 为从这一状态继续行走并最终停在 $2$ 的方案数，其中 $c$ 是到达当前节点并完成变色后的颜色。若 $u=2$，可以选择立即结束，因此先计入一个方案，但仍然要继续枚举下一步。

记 $h(v,c)$ 为到达 $v$ 后的颜色：$v=1$ 时为蓝色，$v=2$ 时为红色，其余情况保持 $c$。令 $A(S,u,p,c)$ 为所有满足以下条件的下一节点 $v$：$v\ne u$，$v\ne p$，有向边 $u\to v$ 的颜色为 $c$，并且 $v\ge3$ 时有 $v\notin S$。转移为

$$F(S,u,p,c)=[u=2]+\sum_{v\in A(S,u,p,c)}F(S',v,u,h(v,c)),$$

其中 $v\ge3$ 时 $S'=S\cup\{v\}$，否则 $S'=S$。答案为 $F(\varnothing,1,0,\text{蓝})$，$0$ 表示不存在前一个节点。所有加法对 $10^9+7$ 取模。

代码用访问标记实现集合：进入一个普通节点时标记，递归返回后撤销；节点 $1,2$ 不设置普通节点访问标记。前一个节点单独保留，用来排除立即折返。每条合法行走对应搜索树中唯一的一个在 $2$ 处选择结束的位置，故不会重计或漏计。

搜索一定有限。两个相邻普通节点之间至多出现两个特殊节点，否则三个连续特殊节点只能形成 $1,2,1$ 或 $2,1,2$。普通节点总共最多使用 $N-2$ 个，递归深度为 $O(N)$。

令 $m=N-2$。时间复杂度可上界为 $O(N\,5^m m!)$：先选择并排列用到的普通节点，每个间隙中的特殊节点序列只能为空、$1$、$2$、$1,2$ 或 $2,1$；每个搜索状态再枚举至多 $N$ 个后继。空间复杂度为 $O(N)$，包括访问标记和递归栈。该方法不合并相同状态，在较大的全白普通节点输入上会超时。

参考代码（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;
  vector<int> used(n);
  auto dfs = [&](auto&& self, int u, int last, bool blue) -> int {
    if (u == 0) blue = true;
    if (u == 1) blue = false;
    int res = (u == 1);
    for (int v = 0; v < n; v++) {
      if (v == u || v == last || (v >= 2 && used[v])) continue;
      bool edge_blue = (u < v) != (s[u] == s[v]);
      if (edge_blue != blue) continue;
      if (v >= 2) used[v] = 1;
      res += self(self, v, u, blue);
      if (res >= mod) res -= mod;
      if (v >= 2) used[v] = 0;
    }
    return res;
  };
  cout << dfs(dfs, 0, -1, true) << '\n';
}

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