Cho hai số nguyên ~n~ và ~k~. Một số Bedao cơ số ~n~ được định nghĩa là một số nguyên dương có thể thu được từ tổng các lũy thừa riêng biệt của ~n~.

Ví dụ: Các số Bedao cơ số ~3~ có thể là ~9 = 3^2~, ~12 = 3^2 + 3^1~, ~37 = 3^3 + 3^2 + 3^0~. Trong khi đó, các số ~2, 5, 8, \ldots~ không phải là số Bedao cơ số ~3~.

Vậy, với hai số ~n~ và ~k~ cho trước, hãy tìm số Bedao cơ số ~n~ thứ ~k~ theo thứ tự tăng dần. Vì kết quả có thể rất lớn nên hãy in ra theo modulo ~10^9 + 7~.

Input

• Dòng đầu tiên gồm một số nguyên dương ~t~ (~1 \le t \le 2\times 10^5~) là số bộ test.

• ~t~ dòng sau, mỗi dòng gồm hai số nguyên dương ~n~ và ~k~ (~2 \le n \le 100~, ~1 \le k \le 10^{18}~).

Output

• In ra ~t~ dòng, mỗi dòng là số Bedao cơ số ~n~ thứ ~k~ trong bộ test đó.

Sample Input 1

3
2 24
3 5
5 2004

Sample Output 1

24
10
12203775

Notes

Ở ví dụ thứ nhất, mọi số đều là số Bedao cơ số ~n=2~, vậy nên số thứ 24 là 24.

Ở ví dụ thứ hai, ~6~ số Bedao cơ số ~n=3~ đầu tiên là ~{1, 3, 4, 9, 10, 13}~ nên đáp án là ~10~.