状态机转移路径计数：可分辨催化剂下的 DAG 取模游走枚举
Regime Transition Path Count: Modular DAG Walk Enumeration with Distinguishable Catalysts
开始编码实现 solution(n: int, edges: list[list[int]], source: int, target: int) -> int。给定 n 个状态节点（id 0..n-1）、一个有向转移边列表 edges（其中 edges[k] = [src, dst] 表示状态 src 可以转移到状态 dst）以及 source 与 target 两个状态 id，返回该状态转移 DAG 中从 source 到 target 的有向路径数对 1_000_000_007 取模的结果。每条路径都是 一组有序的边实例——同一边集的不同顺序算不同路径，且 平行边可分辨（两条 u -> v 平行边对从 u 到 v 的计数贡献 2，因为它们代表两个不同的转移催化剂）。当 source == target 时返回 1（空路径）。当 target 不可达时返回 0。编排器保证无环，但契约依然要求做防御性 Kahn 环检测；若图中任意位置存在环，返回哨兵 -1。
例
solution(4, [[0, 1], [0, 2], [1, 3], [2, 3], [0, 3]], 0, 3) 返回 3。从 0 到 3 共有三条不同路径：直接边 0 -> 3、两跳 0 -> 1 -> 3、两跳 0 -> 2 -> 3。再看平行边：solution(3, [[0, 1], [0, 1], [1, 2]], 0, 2) 返回 2，因为两条 0 -> 1 平行边代表不同的转移催化剂，各自与 1 -> 2 组合成独立的 0 -> 2 游走。空路径边界 solution(1, [], 0, 0) 返回 1，不可达的 solution(3, [[0, 1]], 0, 2) 返回 0（从 0 没有路径能到 2）。
预期解法把邻接表构造成 multiset（每个源节点一个 list[int]，不是 set），跑一遍 Kahn 既验证无环又得到合法的拓扑序，然后在 反向 拓扑序上扫，按 count[u] = sum over each (u -> v) edge instance of count[v] mod 1_000_000_007 填表，基线 count[target] = 1。整体 O(N + M) 时间空间，上限规模下踩在 2000 ms 预算内有充足余量；平行边能正确计数是因为每条都作为独立的项进入对 adj[u] 的求和。set 风格的邻接会在每个有重复边的转移上悄悄把答案减半。
需要明确的契约细节：平行边明确允许，每条都必须贡献到计数（multiset 邻接是关键）。source == target 不论周围有什么边都返回 1（长度为零的游走总是存在）。模 1_000_000_007 只作用在返回的路径数上；可达性和环检测不取模。自环（src == dst）被输入契约禁止，畸形输入下行为未定义。即使环位于与 source -> target 可达分量分离的组件里，也照样返回 -1——任意位置的环都违反了 DAG 假设。
实现细节由 stubs/stub.py 提供。
实践背景
某宏观状态机模型每天把行情归入若干状态之一——低波漂移、趋势、震荡、高波恐慌、均值回归 carry——并从历史里学出一张转移图，描述状态之间的可达关系。风控团队跑情景压力时，要在给定当前状态和两三步之外的目标状态时，统计有多少条可分辨的实际游走能到达该路径。图里的平行边对应一个事实：两个不同催化剂（政策利率冲击 vs 公司财报冲击 vs 突发流动性事件）都能让系统朝同一方向动；团队要把每条催化剂分开计数，因为实际路径取决于哪条催化剂触发，而不是只看终态。对 1_000_000_007 取模可以让长 horizon 下组合爆炸的计数依然落在定长 int 里；上层调用者跨情景比较的是模意义下的计数比例，不是绝对值。防御性的环检测则用来兜底——一份配错的转移矩阵不小心引入了一条反向边，哨兵 -1 就提示编排器停下情景跑、page 建模同事，而不是把发散 DP 出来的乱数交给下游。
约束条件
- 1 <= N <= 2000，N 是状态节点数（id 范围 0..N-1）
- 0 <= M <= 5000，M 是 `edges` 长度
- edges[k] 是二元列表 [src, dst]，src, dst 落在 [0, N-1]，且 src != dst（不允许自环）；允许相同 (src, dst) 的平行边，每条独立计数
- 0 <= source < N 且 0 <= target < N；编排器保证输入图无环，但契约要求依然做防御性环检测，检出环时返回 -1
- 返回类型为 int：路径计数对 1_000_000_007 取模，target 不可达时为 0，source == target 时为 1，检出环时为哨兵 -1
样例
Case 1 · statement-example: 4 regimes, three distinct paths from 0 to 3
输入: [4,[[0,1],[0,2],[1,3],[2,3],[0,3]],0,3]
期望: 3
三条不同 0->3 路径：直接边、经过 1、经过 2，共 3。
Case 2 · statement-example: parallel edges count as distinguishable catalysts
输入: [3,[[0,1],[0,1],[1,2]],0,2]
期望: 2
两条 0->1 平行边代表不同催化剂，分别与 1->2 组合，共 2 条路径。
Case 3 · boundary: source == target with no edges returns 1 (empty walk)
输入: [1,[],0,0]
期望: 1
n=1, source==target，空路径计数 1。
Case 4 · boundary: source == target with edges around still returns 1
输入: [3,[[0,1],[1,2],[0,2]],1,1]
期望: 1
source==target 时空路径计数 1，与周围边无关。
Case 5 · boundary: target unreachable returns 0
输入: [3,[[0,1]],0,2]
期望: 0
从 0 出发到不了 2，返回 0。
Case 6 · boundary: source has no outgoing edges and != target returns 0
输入: [3,[[1,2]],0,2]
期望: 0
source 0 没有出边，到不了 target 2，返回 0。
Case 7 · boundary: target has no incoming edges and != source returns 0
输入: [3,[[0,1]],0,2]
期望: 0
target 2 没有入边，不可达，返回 0。
Case 8 · boundary: 2 nodes, single direct edge
输入: [2,[[0,1]],0,1]
期望: 1
两节点单边，路径数 1。
Case 9 · boundary: 2 nodes, single edge, reversed source/target unreachable
输入: [2,[[0,1]],1,0]
期望: 0
边方向 0->1，从 1 不可达 0，返回 0。
Case 10 · typical: linear chain has exactly one path
输入: [5,[[0,1],[1,2],[2,3],[3,4]],0,4]
期望: 1
线性链上恰有一条路径。
Case 11 · typical: diamond graph counts 2 paths
输入: [4,[[0,1],[0,2],[1,3],[2,3]],0,3]
期望: 2
钻石图：0->1->3 与 0->2->3 共 2 条。
Case 12 · typical: two parallel edges between source and target return 2
输入: [2,[[0,1],[0,1]],0,1]
期望: 2
两条平行边 0->1，分别计数，返回 2。
Case 13 · typical: three parallel edges return 3
输入: [2,[[0,1],[0,1],[0,1]],0,1]
期望: 3
三条平行边各自计数，返回 3。
Case 14 · typical: parallel edges multiply in chain
输入: [3,[[0,1],[0,1],[1,2],[1,2]],0,2]
期望: 4
0->1 两条 × 1->2 两条 = 4 条路径。
Case 15 · adversarial: 3-cycle returns -1 sentinel
输入: [3,[[0,1],[1,2],[2,0]],0,2]
期望: -1
三节点环触发哨兵 -1。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例；服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出；点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: 4 regimes, three distinct paths from 0 to 3
输入: [4,[[0,1],[0,2],[1,3],[2,3],[0,3]],0,3]
期望: 3
三条不同 0->3 路径：直接边、经过 1、经过 2，共 3。
Case 2 · statement-example: parallel edges count as distinguishable catalysts
输入: [3,[[0,1],[0,1],[1,2]],0,2]
期望: 2
两条 0->1 平行边代表不同催化剂，分别与 1->2 组合，共 2 条路径。
Case 3 · boundary: source == target with no edges returns 1 (empty walk)
输入: [1,[],0,0]
期望: 1
n=1, source==target，空路径计数 1。
Case 4 · boundary: source == target with edges around still returns 1
输入: [3,[[0,1],[1,2],[0,2]],1,1]
期望: 1
source==target 时空路径计数 1，与周围边无关。
Case 5 · boundary: target unreachable returns 0
输入: [3,[[0,1]],0,2]
期望: 0
从 0 出发到不了 2，返回 0。
Case 6 · boundary: source has no outgoing edges and != target returns 0
输入: [3,[[1,2]],0,2]
期望: 0
source 0 没有出边，到不了 target 2，返回 0。
Case 7 · boundary: target has no incoming edges and != source returns 0
输入: [3,[[0,1]],0,2]
期望: 0
target 2 没有入边，不可达，返回 0。
Case 8 · boundary: 2 nodes, single direct edge
输入: [2,[[0,1]],0,1]
期望: 1
两节点单边，路径数 1。
Case 9 · boundary: 2 nodes, single edge, reversed source/target unreachable
输入: [2,[[0,1]],1,0]
期望: 0
边方向 0->1，从 1 不可达 0，返回 0。
Case 10 · typical: linear chain has exactly one path
输入: [5,[[0,1],[1,2],[2,3],[3,4]],0,4]
期望: 1
线性链上恰有一条路径。
Case 11 · typical: diamond graph counts 2 paths
输入: [4,[[0,1],[0,2],[1,3],[2,3]],0,3]
期望: 2
钻石图：0->1->3 与 0->2->3 共 2 条。
Case 12 · typical: two parallel edges between source and target return 2
输入: [2,[[0,1],[0,1]],0,1]
期望: 2
两条平行边 0->1，分别计数，返回 2。
Case 13 · typical: three parallel edges return 3
输入: [2,[[0,1],[0,1],[0,1]],0,1]
期望: 3
三条平行边各自计数，返回 3。
Case 14 · typical: parallel edges multiply in chain
输入: [3,[[0,1],[0,1],[1,2],[1,2]],0,2]
期望: 4
0->1 两条 × 1->2 两条 = 4 条路径。
Case 15 · adversarial: 3-cycle returns -1 sentinel
输入: [3,[[0,1],[1,2],[2,0]],0,2]
期望: -1
三节点环触发哨兵 -1。