Birthday Gift Sequence

Donghyeok has $N$ friends. They wanted to give him a sequence for his birthday, but the sequence has far too many terms, so each friend gave him one number $x$ together with the rule for building the sequence from it. Today the friends want to ask what the $K$-th term of their sequence is. Donghyeok memorized none of it, so compute the answers for him.

The sequence $M_i$ built from the number $x_i$ given by the $i$-th friend follows this rule. Let $A = \{x_i^0, x_i^1, x_i^2, \dots\}$ be the set of the powers of $x_i$. List every non-empty finite subset of $A$ as $A_0, A_1, A_2, \dots$, and let $a_j$ be the sum of all elements of the subset $A_j$. The sequence $M_i$ is the list of those values $a_j$ sorted in increasing order, and no value appears twice.

For example, with $x = 3$ the set is $A = \{1, 3, 9, 27, \dots\}$ and the subset sums in increasing order give $M = 1, 3, 4, 9, 10, 12, 13, \dots$.

The first line contains the number of friends $N$ ($1 \le N \le 100{,}000$).

Each of the next $N$ lines contains the number $x$ ($2 \le x \le 1{,}000$) given by a friend and the position $K$ ($1 \le K \le 1{,}000{,}000{,}000$) that friend asks about, separated by a space.

For every friend, take the $K_i$-th term of the sequence $M_i$ built from $x_i$, add all of those terms together, and print the remainder of that total divided by $1{,}000{,}000{,}007$ on the first line.