ID - MarisaOJ: Marisa Online Judge

ID

Time limit: 1000 ms
Memory limit: 256 MB
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 ```