Các phòng máy tính được đánh số ~0,1,2,\dots~ và các máy tính trong mỗi phòng được đánh số ~1,2,3,\dots~.

Nếu một đội thi tại phòng máy số ~n~ và sử dụng máy tính số ~k~, mật khẩu đăng nhập của đội là ~\rho(n,k)~, được xác định như sau:

~\displaystyle \rho(n,k)= \begin{cases} 1, & \text{nếu } n=0,\\[4pt] \frac{k\cdot\left(\rho(0,k)+\rho(1,k)+\dots+\rho(n-1,k)\right)}{n}, & \text{nếu } n\ge 1. \end{cases}~

Kết quả được lấy theo mô đun ~10^9+7~.

Yêu cầu: Cho danh sách ~m~ đội thi, biết đội thứ ~i~ thi tại phòng máy số ~n_i~ và sử dụng máy tính số ~k_i~. Hãy tìm mật khẩu của mỗi đội.

Input

• Dòng đầu tiên chứa số nguyên ~m~ ~(1 \le m \le 2\cdot 10^5)~;

• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~n_i,k_i~ ~(1 \le n_i,k_i \le 2\cdot 10^5)~.

Output

Gồm ~m~ dòng, dòng thứ ~i~ chứa mật khẩu của đội thứ ~i~ theo mô đun ~10^9+7~.

Scoring

Sample Input 1

5
1 6688
2 2022
5 2023
7 8888
3 2023

Sample Output 1

6688
2045253
892990352
33049279
381911293