按原规则枚举行走（通过子任务 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();
}