Comet OJ

C0563 [BJOI2018]治疗之雨

内存限制：512 MB 时间限制：2000 ms

题目描述

（没玩过《炉石传说》的人可以跳过这一段）今天我们来探讨下《炉石传说》中“治疗之雨”（恢复 $12$ 点生命值，随机分配到所有友方角色上）和“暗影打击装甲”（每当一个角色获得治疗，便对随机敌人造成 $1$ 点伤害）这两张卡牌之间的互动效果。假设你场上有 $m$ 个剩余生命值无限大且生命值上限减去剩余生命值也无限大的随从，而对方的场上有 $k$ 个暗影打击装甲，你的英雄剩余生命值为 $p$、生命值上限为 $n$，现在你使用了一张可以恢复无限多（而不是 $12$ 点）生命值的治疗之雨，问治疗之雨期望总共恢复了几点生命值以后你的英雄会死亡（生命值降为 $0$；治疗之雨的判定机制使得在此后再也不会为英雄恢复生命值）。

注：题目背景与题目描述有冲突的地方请以题目描述为准

下面让我们再形式化地描述一遍问题。

你现在有 $m+1$ 个数：第一个为 $p$，最小值为 $0$，最大值为 $n$；剩下 $m$ 个都是无穷，没有最小值或最大值。你可以进行任意多轮操作，每轮操作如下：

在不为最大值的数中等概率随机选择一个（如果没有则不操作），把它加一；

进行 $k$ 次这个步骤：在不为最小值的数中等概率随机选择一个（如果没有则不操作），把它减一。

现在问期望进行多少轮操作以后第一个数会变为最小值 $0$。

输入格式

输入包含多组数据。

输入第一行包含一个正整数 $T$，表示数据组数。

接下来 $T$ 行 ，每行 $4$ 个非负整数 $n$、$p$、$m$、$k$（含义见题目描述），表示一次询问。

输出

输出 $T$ 行，每行一个整数，表示一次询问的答案。

如果无论进行多少轮操作，第一个数都不会变为最小值 $0$，那么输出-1；

否则，可以证明答案一定为有理数，那么请输出答案模 $1000000007$ 的余数，即设答案为 $\frac{a}{b}$（$a$、$b$ 为互质的正整数 ），你输出的整数为 $x$，那么你需要保证 $0 \leq x < 1000000007$ 且 $a \equiv bx \bmod\ 1000000007$。

样例

样例输入 1

2
2 1 1 1
2 2 1 1

样例输出 1

6
8

提示

【数据范围与提示】

对于 $10\%$ 的数据，$n \leq 3$，$m, k \leq 2$。

对于 $20\%$ 的数据，$n, m, k \leq 5$。

对于 $30\%$ 的数据，$n, m, k \leq 30$。

对于 $40\%$ 的数据，$n, m, k \leq 50$。

对于 $50\%$ 的数据，$n, m, k \leq 200$。

对于 $70\%$ 的数据，$n \leq 200$。

对于 $80\%$  的数据，$n \leq 500$。

对于 $100\%$ 的数据，$1 \leq T \leq 100$，$1 \leq p \leq n \leq 1500$，$0 \leq m, k \leq 1000000000$。

// 保证不存在 $n=p=k=1$，$m=0$ 的情况（因为出题人判错了）

// 保证不存在答案的分母是 $1000000007$ 的倍数的情况（因为出题人没想到）