题目描述

公园里出现了一台抽奖机！根据小道消息，抽奖机在接下来的 $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$ 取模的结果。

7
1 2
2 1
5 3
10 15
347 1562
724 15
283917 192034

1
0
2
400
87949316
1579768
172877821

提示

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\leq T\leq 5\times 10^3$，$1\leq n,w\leq10^6$。