The problem describes a function $f(n, k)$ defined by the formula:
- $f(n, k) = 1$ if $n = 0$.
- $f(n, k) = \frac{k \times (f(0, k) + f(1, k) + \ldots + f(n - 1, k))}{n}$ if $n \geq 1$.
You are given $M$ queries, each consisting of two integers $n, k$. The task is to compute $f(n, k)$ for each query.
### Input
- The first line contains a positive integer $M (1 \leq M \leq 2 \times 10^5)$.
- The next $M$ lines each contain two integers $n, k (1 \leq n, k \leq 2 \times 10^5)$ representing a query.
### Output
- For each query, print a line containing the result of $f(n, k)$ modulo $10^9+7$.
### Constraints
- 20% of the tests have $M \leq 2 \times 10^5, n \leq 3, k \leq 2 \times 10^5$.
- 20% of the tests have $M \leq 2 \times 10^5, n + k \leq 65$.
- 30% of the tests have $M, n, k \leq 5 \times 10^3$.
- The remaining 30% of the tests have no additional constraints.
### Example
Input:
```
4
1 13
2 213
5 45
7 56879
```
Output:
```
13
22791
1906884
538958503
```
