T332605 [MHLOI Round #2] 阶梯计划

**“用资源改变原理？”** **“绕开原理。”** [阶梯计划](https://santi.huijiwiki.com/wiki/%E9%98%B6%E6%A2%AF%E8%AE%A1%E5%88%92) 最早是为了获得三体人的情报，于是 [PIA](https://santi.huijiwiki.com/wiki/%E8%A1%8C%E6%98%9F%E9%98%B2%E5%BE%A1%E7%90%86%E4%BA%8B%E4%BC%9A%E6%88%98%E7%95%A5%E6%83%85%E6%8A%A5%E5%B1%80) 决定向三体舰队发射探测器。后来因飞船的特殊性质无法进行减速，被彻底否决。但 [托马斯·维德](https://santi.huijiwiki.com/wiki/%E6%89%98%E9%A9%AC%E6%96%AF%C2%B7%E7%BB%B4%E5%BE%B7) 决定将一个人类（后改为人类大脑）用此飞行器送进三体人的“心脏”。 阶梯计划飞行器质量极小，本身没有推进能力，有一个面积巨大的帆使用纳米材料“飞刃”做成的绳固定在飞行器上。并将核弹部署在飞行轨道上，利用核弹爆炸加速。理论上可以达到光速的百分之一。由于每次爆炸都会让速度提高一个阶层，像是在攀登一道阶梯，因此命名为“阶梯计划”。

阶梯计划一共有 $N$ 个阶段，每个阶段都会引爆 $N^2$ 个核弹 其中，在第 $i$ 阶段的第 $j$ 个核弹产生的威力是 $(ij)^S$ ，而在第 $i$ 阶段产生的总威力是所有核弹的威力的总和 在第 $i$ 阶段产生的推动力是在 $i$ 阶段产生的总威力乘以 $r^i$ 总推动力是所有阶段的推动力的加和 问：总推动力对 $10^9+7$ 取模的结果

第 $1$ 行一个正整数 $T$ ，表示数据组数 第 $2\sim T+1$ 行，每行一个询问，依次表示 $N,S,r$ ， $N,S,r$ 均为正整数

对于每个询问，输出一行一个整数表示对应答案

### 本题子任务丰富，请选择性答题。 对于所有 $Subtask$ ， $T=1,r\le 10^9,S\le 10^9,N\le7000$ 。 $Subtask(\# 1)$ ： $S=0$ $Subtask(\# 2)$ ： $S=1$ $Subtask(\# 3)$ ： $S=2$ $Subtask(\# 4)$ ： $r=0$ $Subtask(\# 5)$ ： $N\le7000$ $Subtask(\# 6)$ ： $N\le100$ $Subtask(\# 7)$ ： $N\le10^3$ $Subtask$ 测试点个数及分数如下表： | $Subtask#?$ | 测试点个数 | 每个测试点的分数 | | -----------: | -----------: | -----------: | | 1 | 1 | 5 | | 2 | 1 | 6 | | 3 | 1 | 7 | | 4 | 1 | 2 | | 5 | 6 | 8 | | 6 | 2 | 8 | | 7 | 2 | 8 |