只有一个黑点时的分块计数（通过子任务 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();
}