P13791 「CZOI-R6」抽奖

公园里出现了一台抽奖机！根据小道消息，抽奖机在接下来的 $n$ 天的某一天晚上会撤走。抽奖机最终在每天晚上撤走的概率都相等。 你想在这 $n$ 天进行抽奖。初始时，你有一个中奖概率 $p = 0$。 每一天上午，你都会积攒运气，使得 $p$ 增加 $\frac{1}{n}$。 每一天下午，你都可以选择抽奖或不抽奖。若抽奖，设当前为第 $i$ 天，则你需要花费 $\frac{n}{n-i+1}$ 的代价，以 $p$ 的概率使得你的收益增加 $w$，且让 $p$ 重置为 $0$。$w$ 是一个固定的常量。 你制订了一个最优的策略以最大化你获得的收益减你付出的代价。你想知道假如你按照此策略，期望的收益减代价为多少。 **出于某种原因，你需要输出期望值乘 $\boldsymbol{n^2}$ 后对 $\boldsymbol{10^9 + 7}$ 取模的结果**。

**本题有多组测试数据。** 第一行 $1$ 个整数 $T$，表示数据组数。 接下来 $T$ 行，每行 $2$ 个整数，依次为 $n, w$。

输出 $T$ 行。每行输出 $1$ 个整数，表示期望值乘 $n^2$ 后对 $10^9 + 7$ 取模的结果。

**【数据范围】** **本题采用捆绑测试。** | 子任务编号 | $T \leq$ | $n \leq$ | $w \leq$ | 分值 | | :--------: | :------------: | :------: | :-------------: | :--: | | $1$ | $5$ | $20$ | $50$ | $15$ | | $2$ | $5$ | $10^3$ | $3 \times 10^3$ | $15$ | | $3$ | $20$ | $10^6$ | $10^6$ | $30$ | | $4$ | $5\times 10^3$ | $10^6$ | $10^6$ | $40$ | 对于 $100\%$ 的数据，$1\leq T\leq 5\times 10^3$，$1\leq n,w\leq10^6$。