市场状态路径计数：恐慌须由平静隔开

某个量化研究员把市场宏观状态简化成 k 个互斥的「regime」字符串（例如 ['calm', 'bull', 'bear', 'panic']），并用一个 n 步的离散时间模型描述一条市场路径——每一步从 regimes 里独立挑一个 regime，所以总共有 k^n 条不同的路径。研究员关心一个特定的「危机情景」子集合：长度恰好 n 的路径中，**'panic' 出现至少 2 次，并且任意两次相邻的 'panic' 之间至少夹着一次 'calm'（也就是说市场不能在没有「平静」缓冲的情况下连续两次进入恐慌）。请算出满足这两条约束的路径总数**。

请实现 solution(n: int, regimes: list[str]) -> int。n 是路径长度，regimes 是这一步可以选的 regime 列表（保证两两不同）。返回所有合法路径的数量。如果 'panic' 不在 regimes 里，路径里凑不出 2 次 panic，返回 0；如果 'panic' 在里面但 'calm' 不在，「相邻 panic 之间至少一次 calm」这条约束就永远不可能被满足（一旦放第二个 panic 就违规），同样返回 0。

举例：solution(3, ['calm', 'panic']) 应返回 1。n = 3 时 8 条路径里只有 ('panic', 'calm', 'panic') 同时满足「≥ 2 次 panic」和「相邻 panic 之间有 calm」。('calm', 'panic', 'panic')、('panic', 'panic', 'calm')、('panic', 'panic', 'panic') 这几条 panic 数量虽然达标但相邻 panic 之间没有 calm 隔开，全都不算。再举一例：solution(4, ['calm', 'bull', 'panic']) 应返回 7，包括 ('calm','panic','calm','panic')、('bull','panic','calm','panic')、('panic','calm','calm','panic')、('panic','calm','bull','panic')、('panic','calm','panic','calm')、('panic','calm','panic','bull')、('panic','bull','calm','panic')。

朴素的 DFS 是分支因子 k、深度 n 的递归树，叶子级别 O(k^n)。n = 30、k = 4 已经是 1e18 量级，必然超时。正解是带记忆化的递归（也即 DP）：递归状态只有 (i, p, can_panic) 三个分量，其中 i 是当前步数，p 是已出现的 panic 次数（一旦 ≥ 2 就截断保留为 2，因为后面的 panic 数量对约束没有进一步影响），can_panic 是布尔——表示「上一次 panic 之后是否已经经历至少一次 calm」（panic 还没出现过时约定为 True，允许第一次 panic 落地）。每个状态的转移只需扫一遍 regimes，状态数 O(n)，总复杂度 O(n * k)。