1. 题意转化

我们有 ( m+1 ) 个数：

• 第一个数 ( x_0 )，范围是 ([0, n])，初始为 ( p )，最小值 ( 0 )，最大值 ( n )。
• 其他 ( m ) 个数是“无穷大”，没有上限，也没有下限（因为题中说“剩余生命值无限大且生命值上限减去剩余生命值也无限大”，意思是它们可以无限加血，也可以无限受伤，所以它们永远不会达到最大或最小限制）。

每轮操作：

1. 加血阶段：在所有不为最大值的数中，等概率随机选一个，给它加 1。

   • 对于 ( x_0 )，如果它等于 ( n )，则不会被选。
   • 对于其他 ( m ) 个数，它们永远不是最大值（因为没上限），所以总是候选。
   • 因此候选集合大小是：
     • 如果 ( x_0 < n )，候选数有 ( m+1 ) 个。
     • 如果 ( x_0 = n )，候选数有 ( m ) 个。

2. 扣血阶段：进行 ( k ) 次独立操作：在不为最小值的数中等概率随机选一个，减 1。

   • 对于 ( x_0 )，如果它等于 0，则不会被选（已经死了，但题目里说英雄死亡后不会再给它加血，但这里还没死时它可能被扣血）。
   • 对于其他 ( m ) 个数，它们永远不是最小值（因为没下限），所以总是候选。
   • 因此候选集合大小是：
     • 如果 ( x_0 > 0 )，候选数有 ( m+1 ) 个。
     • 如果 ( x_0 = 0 )，候选数有 ( m ) 个。

---

2. 状态与转移

我们只关心 ( x_0 ) 的值，因为其他 ( m ) 个数是无限的，它们的值不影响概率（它们永远不会因为达到上下界而退出候选）。

设 ( E[i] ) 表示当前 ( x_0 = i ) 时，期望还要进行多少轮，英雄会死亡（即 ( x_0 ) 变为 0）。

边界： [ E[0] = 0 ] 我们要求 ( E[p] )。

---

2.1 加血阶段概率

在状态 ( i )（( 0 < i < n )）：

• 候选数总数 = ( m+1 )。
• 选到 ( x_0 ) 的概率 = ( \frac{1}{m+1} )，此时 ( i \to i+1 )。
• 选到其他 ( m ) 个数的概率 = ( \frac{m}{m+1} )，此时 ( x_0 ) 不变。

在状态 ( i = n )：

• 候选数总数 = ( m )。
• 选到 ( x_0 ) 的概率 = 0（因为它是最大值）。
• 选到其他数的概率 = 1，此时 ( x_0 ) 不变。

---

2.2 扣血阶段概率

扣血阶段进行 ( k ) 次独立操作，每次：

在状态 ( i )（( i > 0 )）：

• 候选数总数 = ( m+1 )。
• 选到 ( x_0 ) 的概率 = ( \frac{1}{m+1} )，扣 1 血。
• 选到其他数的概率 = ( \frac{m}{m+1} )，( x_0 ) 不变。

在状态 ( i = 0 )：

• 候选数总数 = ( m )。
• 选到 ( x_0 ) 的概率 = 0。
• 选到其他数的概率 = 1。

---

2.3 一轮的转移

一轮 = 一次加血 + ( k ) 次扣血。

在 ( 0 < i < n )：

加血：

• 以概率 ( A = \frac{1}{m+1} ) 加血到 ( i+1 )（然后扣血阶段在这个新状态进行）。
• 以概率 ( B = \frac{m}{m+1} ) 加血到 ( i )（然后扣血阶段在这个状态进行）。

但这样直接考虑一整轮比较麻烦，因为加血和扣血不是独立的顺序。更好的方法是：先考虑加血对状态的影响，再考虑扣血对状态的影响。

---

更清晰的建模

设 ( P_{\text{inc}}(i) ) = 在状态 ( i ) 时，加血阶段结束后 ( x_0 ) 的分布。

设 ( P_{\text{dec}}(j) ) = 在状态 ( j ) 时，经过 ( k ) 次独立扣血后的分布。

那么一轮的转移矩阵 ( T ) 是： [ T(i, j) = \sum_{t} P_{\text{inc}}(i, t) \cdot P_{\text{dec}}(t, j) ]

---

加血阶段（状态 ( i )）：

• 如果 ( i < n )：
  • 到 ( i+1 ) 的概率 = ( \frac{1}{m+1} )。
  • 到 ( i ) 的概率 = ( \frac{m}{m+1} )。
• 如果 ( i = n )：
  • 到 ( n ) 概率 = 1。

---

扣血阶段（状态 ( j ) 经过 ( k ) 次独立操作）：

每次操作：

• 如果 ( j > 0 )：
  • 到 ( j-1 ) 的概率 = ( \frac{1}{m+1} )。
  • 到 ( j ) 的概率 = ( \frac{m}{m+1} )。
• 如果 ( j = 0 )：
  • 到 ( 0 ) 概率 = 1。

---

所以扣血阶段是一个二项分布的效果：

从状态 ( j ) 开始，经过 ( k ) 次操作，每次有概率 ( q = \frac{1}{m+1} ) 减 1，概率 ( 1-q ) 不变。

因此从 ( j ) 到 ( j - r ) 的概率 = [ \binom{k}{r} q^r (1-q)^{k-r}, \quad 0 \le r \le \min(j, k) ] 如果 ( r > j )，则不能降到负数以下，但这里 ( j ) 有限，所以最多降到 0。

实际上，如果 ( j - r < 0 )，则概率归到 0。

---

2.4 动态规划方程

设 ( E[i] ) 表示从 ( i ) 开始到死亡的期望轮数。

一轮后：

• 先加血（可能到 ( i ) 或 ( i+1 )），
• 然后扣血（可能降若干点）。

所以： 对于 ( 0 < i < n )：

加血后：

• 以概率 ( \frac{1}{m+1} ) 到 ( i+1 )，
• 以概率 ( \frac{m}{m+1} ) 到 ( i )。

然后从状态 ( s )（( s = i ) 或 ( i+1 )）经过 ( k ) 次扣血到状态 ( t ) 的概率是 ( \text{Dec}(s, t) )。

所以： [ E[i] = 1 + \frac{1}{m+1} \sum_{t=0}^{i+1} \text{Dec}(i+1, t) E[t] + \frac{m}{m+1} \sum_{t=0}^{i} \text{Dec}(i, t) E[t] ] 其中 ( \text{Dec}(s, t) = \binom{k}{s-t} q^{s-t} (1-q)^{k-(s-t)} ) 当 ( s-t \ge 0 ) 且 ( k \ge s-t )，否则 0，并且 ( t \ge 0 )。

对于 ( i = n )：

加血后一定在 ( n )，所以： [ E[n] = 1 + \sum_{t=0}^{n} \text{Dec}(n, t) E[t] ]

对于 ( i = 0 )： [ E[0] = 0 ]

---

3. 问题规模与解法

• ( n \le 1500 )。
• ( m, k ) 可以很大（到 ( 10^9 )），但 ( q = \frac{1}{m+1} ) 可能很小。
• 由于 ( n ) 不大，我们可以直接解这个线性方程组，用高斯消元 O(n³) 在 n=1500 时不可行，但注意转移是带状的，每行非零元素 O(k)？其实不是，因为从 i 可能跳到 i+1 再扣血到较远的位置，但扣血最多 k 步，所以非零元素 O(k) 个，但 k 可能很大，不过当 k>n 时，最多扣到 0，所以非零元素 O(min(k,n))。

实际上，从状态 i 出发，一轮后能到达的状态范围是 [max(0, i - k), min(n, i+1)]，所以每行非零元素 O(min(k,n)+2) 个，当 n=1500 时，用带状高斯消元 O(n * 带宽²) 可过。

---

4. 特殊情况

• 如果 ( m=0 ) 且 ( k\ge 1 )：
  加血阶段只有英雄可选（如果英雄未满血），但扣血阶段也只有英雄可选（如果英雄>0），所以英雄一定在有限步内死亡，除非加血永远不加到英雄（即英雄满血且不加血）——但初始 p<n 时，会加血，然后扣血，最终死亡。
  若 p=n，则加血不会选英雄，但扣血会选英雄（因为英雄>0），所以英雄会一直扣血到 0。
  所以不会出现 -1，除非 k=0 且 m=0 且 p=n，但题目保证没有 n=p=k=1, m=0。

• 如果 ( k=0 )：
  那么永远不会扣血，英雄永远不会死，输出 -1。

• 如果 ( m ) 很大，( q ) 很小，扣血打到英雄的概率很小，但期望仍有限，因为只要 k>0，就有概率死亡。

---

5. 模意义下的计算

我们需要模 ( 10^9+7 ) 意义下的答案。

• 二项系数 ( \binom{k}{r} ) 对 ( k ) 很大时，可用公式： [ \binom{k}{r} = \frac{k (k-1) \dots (k-r+1)}{r!} ] 模 ( 10^9+7 ) 计算，因为 r ≤ n ≤ 1500，所以可以 O(r) 计算。

• ( q^r (1-q)^{k-r} ) 中 ( q = \frac{1}{m+1} )，需要模逆元。

---

6. 实现思路

1. 预处理阶乘和逆元到 1500（用于组合数分母）。
2. 对每个状态 i 从 n 到 1 倒序求解（因为 E[0]=0 已知，可以递推？不行，因为可能从 i 到 i+1，所以必须解方程组）。
3. 构建 n+1 个变量的线性方程组，用高斯消元求解，但利用带状结构优化。
4. 注意判断无解情况（即 k=0 时输出 -1）。

---

核心难点：

• 处理大 k 大 m 时的组合数模运算。
• 带状高斯消元。