#2513. 「BJOI2018」治疗之雨

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: oscar

题目描述

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

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

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

你现在有 m+1m+1 个数:第一个为 pp ,最小值为 00 ,最大值为 nn ;剩下 mm 个都是无穷,没有最小值或最大值。你可以进行任意多轮操作,每轮操作如下:

在不为最大值的数中等概率随机选择一个(如果没有则不操作),把它加一;

进行 kk 次这个步骤:在不为最小值的数中等概率随机选择一个(如果没有则不操作),把它减一。

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

输入格式

输入包含多组数据。

输入第一行包含一个正整数 TT ,表示数据组数。

接下来 TT 行 ,每行 44 个非负整数 nnppmmkk (含义见题目描述),表示一次询问。

输出格式

输出 TT 行,每行一个整数,表示一次询问的答案。

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

否则,可以证明答案一定为有理数,那么请输出答案模 10000000071000000007 的余数,即设答案为 ab\frac{a}{b}aabb 为互质的正整数 ),你输出的整数为 xx ,那么你需要保证 0x<10000000070 \leq x < 1000000007abxmod 1000000007a \equiv bx \bmod\ 1000000007

样例

样例输入 1

2
2 1 1 1
2 2 1 1

样例输出 1

6
8

数据范围与提示

对于 10%10\% 的数据, n3n \leq 3m,k2m, k \leq 2

对于 20%20\% 的数据, n,m,k5n, m, k \leq 5

对于 30%30\% 的数据, n,m,k30n, m, k \leq 30

对于 40%40\% 的数据, n,m,k50n, m, k \leq 50

对于 50%50\% 的数据, n,m,k200n, m, k \leq 200

对于 70%70\% 的数据, n200n \leq 200

对于 80%80\% 的数据, n500n \leq 500

对于 100%100\% 的数据, 1T1001 \leq T \leq 1001pn15001 \leq p \leq n \leq 15000m,k10000000000 \leq m, k \leq 1000000000

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

//保证不存在答案的分母是10000000071000000007的倍数的情况(因为出题人没想到)