생일 선물 수열

동혁이에게는 친구가 $N$명 있다. 친구들은 동혁이의 생일에 수열을 선물하려 했지만, 수열을 이루는 수가 너무 많아서 수열 전체 대신 수열을 만들 수 있는 수 $x$ 하나와 만드는 방법만 알려 줬다. 오늘 친구들은 각자 선물한 수열의 $K$번째 수를 물어보려 한다. 동혁이는 수열을 하나도 외우지 못했으니 대신 답을 구해 주자.

$i$번째 친구가 선물한 수 $x_i$로 만드는 수열 $M_i$의 규칙은 다음과 같다. $x_i$의 거듭제곱을 원소로 하는 집합을 $A = \{x_i^0, x_i^1, x_i^2, \dots\}$라 하자. $A$의 공집합이 아닌 유한 부분집합을 모두 나열해 $A_0, A_1, A_2, \dots$라 하고, 부분집합 $A_j$의 원소를 모두 더한 값을 $a_j$라 하자. 수열 $M_i$는 이 $a_j$를 오름차순으로 정렬한 것이며, 같은 값이 두 번 나오지 않는 증가수열이다.

예를 들어 $x = 3$이면 $A = \{1, 3, 9, 27, \dots\}$이고, 부분집합의 합을 작은 것부터 적으면 $M$은 $1, 3, 4, 9, 10, 12, 13, \dots$이 된다.

첫째 줄에 친구의 수 $N$ ($1 \le N \le 100{,}000$)이 주어진다.

이어지는 $N$개의 줄에는 친구가 선물한 수 $x$ ($2 \le x \le 1{,}000$)와 친구가 묻고 싶은 순번 $K$ ($1 \le K \le 1{,}000{,}000{,}000$)가 공백으로 구분되어 한 줄에 하나씩 주어진다.

친구마다 자신이 선물한 수 $x_i$로 만든 수열 $M_i$의 $K_i$번째 수를 구한 뒤, 그 값을 모두 더한 결과를 $1{,}000{,}000{,}007$로 나눈 나머지를 첫째 줄에 출력한다.