CF1184D2 Parallel Universes (Hard)

Heidi 很喜欢进行模拟，因为她能准确地知道新宇宙何时、何地诞生，以及不存在的链接何时、何地断裂。 然而，多元宇宙本身的运行方式却充满神秘。实际上，它是基于概率运行的，而对某些人来说，这本身就很神秘。 在每个单位时间内，当做出决策时，将随机发生以下两种事件之一。设 $l$ 为当前多元宇宙的长度。以概率 $p_{create} = 1 - \frac{l}{m}$ 诞生一个新宇宙；以概率 $p_{break} = \frac{l}{m}$ 在某个位置断开一个不存在的链接。 更具体地说： - 当诞生一个新宇宙时，它会出现在任意两个相邻宇宙之间，或在多元宇宙的两端。每个位置出现的概率均为 $\frac{1}{l+1}$。 - 当断开一个链接时，可以在任意两个相邻宇宙之间断开，每个位置断开的概率均为 $\frac{1}{l-1}$。断开后，多元宇宙被分为两段，不包含 Doctor 的那一段将消失。 与之前一样，Doctor 始终停留在同一个宇宙中。然而，如果某一时刻多元宇宙断裂，使得 Doctor 处于最左端或最右端，则 TARDIS 将停止工作。 在这种情况下，Doctor 必须亲自穿越多元宇宙，寻找修复工具。 我们关心的是，当上述事件发生时，多元宇宙长度的期望值。

第一行包含三个整数 $n$、$k$ 和 $m$，分别表示多元宇宙的初始长度、Doctor 的初始位置和多元宇宙的最大可能长度，满足 $1 \leq k \leq n \leq m \leq 250$。

输出一个整数，表示多元宇宙长度的期望值。 如果答案为 $\frac{p}{q}$，请输出 $r$，其中 $p \equiv r \cdot q \pmod{10^9 + 7}$。

对于第一和第二个测试点，在没有任何变化的情况下，Doctor 已经处于多元宇宙的某一端。 对于第三个测试点，多元宇宙只能在一个位置断裂，这会使 Doctor 处于某一端。 对于第四个测试点，情况似乎更复杂，因为多元宇宙可能会增长，然后再次断裂。 由 ChatGPT 4.1 翻译