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(n−1,k))n if n≥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≤M≤2×105).
- The next M lines each contain two integers n,k(1≤n,k≤2×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 M≤2×105,n≤3,k≤2×105.
- 20% of the tests have M≤2×105,n+k≤65.
- 30% of the tests have M,n,k≤5×103.
- The remaining 30% of the tests have no additional constraints.
### Example
Input:
41132213545756879
Output:
13227911906884538958503