题目背景

2024 年 12 月 18 日，《炉石传说》31.2.2 补丁上线，水上舞者索尼娅遭到削弱。现在，在这道题目中，你打开时空之门，回到了水索被削弱前的时候。

题目描述

你的场上有 $k$ 个【水上舞者索尼娅】，你的手牌中有 $1$ 张法力值消耗为 $1$ 的【一串香蕉（还剩 $n$ 根）】，你有无尽的法力值，你的手牌数量没有上限。

在你的场上有 $k$ 个【水上舞者索尼娅】的情况下：

当你使用 $1$ 张法力值消耗为 $1$ 的【一串香蕉（还剩 $x$ 根）】时，你将得到：

• $k$ 张法力值消耗为 $0$ 的【一串香蕉（还剩 $x$ 根）】。
• $1$ 张法力值消耗为 $1$ 的【一串香蕉（还剩 $x-1$ 根）】。（若 $x=1$，则不会得到）

当你使用 $1$ 张法力值消耗为 $0$ 的【一串香蕉（还剩 $x$ 根）】时，你将得到：

• $1$ 张法力值消耗为 $1$ 的【一串香蕉（还剩 $x-1$ 根）】。（若 $x=1$，则不会得到）

你一共可以使用多少次【一串香蕉】？

由于答案可能很大，你只需求出答案对 $10^9+7$ 取模的余数。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示数据组数。

对于每组数据：

一行两个正整数 $n,k$。

输出格式

对于每组数据：

输出一行一个整数，表示答案对 $10^9+7$ 取模的余数。

3
2 2
3 1
12 34

12
14
178629506

提示

$1\le T\le10^5$， $1\le n,k\le10^9$。

【样例解释】

对于第 $1$ 组数据：

场上有 $2$ 个【水上舞者索尼娅】，初始手牌中有 $1$ 张法力值消耗为 $1$ 的【一串香蕉（还剩 $2$ 根）】。

使用：$1$ 张法力值消耗为 $1$ 的【一串香蕉（还剩 $2$ 根）】。
手牌：

• $2$ 张法力值消耗为 $0$ 的【一串香蕉（还剩 $2$ 根）】。
• $1$ 张法力值消耗为 $1$ 的【一串香蕉（还剩 $1$ 根）】。

使用：$2$ 张法力值消耗为 $0$ 的【一串香蕉（还剩 $2$ 根）】。
手牌：

• $3$ 张法力值消耗为 $1$ 的【一串香蕉（还剩 $1$ 根）】。

使用：$3$ 张法力值消耗为 $1$ 的【一串香蕉（还剩 $1$ 根）】。
手牌：

• $6$ 张法力值消耗为 $0$ 的【一串香蕉（还剩 $1$ 根）】。

使用：$6$ 张法力值消耗为 $0$ 的【一串香蕉（还剩 $1$ 根）】。
手牌：

• 空

共使用 $1+2+3+6=12$ 张【一串香蕉】。