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)=k×(f(0,k)+f(1,k)++f(n1,k))n if n1. 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(1M2×105). - The next M lines each contain two integers n,k(1n,k2×105) representing a query. ### Output - For each query, print a line containing the result of f(n,k) modulo 109+7. ### Constraints - 20% of the tests have M2×105,n3,k2×105. - 20% of the tests have M2×105,n+k65. - 30% of the tests have M,n,k5×103. - The remaining 30% of the tests have no additional constraints. ### Example Input: 41132213545756879 Output: 13227911906884538958503