You are given a number X. Let us define an array A. You have a sequence X^0, X^1, X^2, ..... Take 0 item, 1 item, 2 items, ...... per every time and  sum them up.  These sums are the elements of array A.
Sort A in increasing order. You are given a number n. You have to print the number in the n-th position. [0 - indexed]

For example, let x = 2. Then the array A = {0, 2^0, 2^1, 2^0 + 2^1, 2^2, .....} or A = {0,1,2,3,4, .....}.

Input

The input begins with the number t of test cases in a single line (t<=10^5). In each of the next t lines there are two numbers x and n (0 <= x, n <= 2^63)  separated by a space.

Output

Just print the desired number in the n-th position of the array. As the number can very big; output the answer modulo 10000009.

Example

Input:
2
2 4
5 10

Output:
4
130

Judge Data is Huge. Use faster I/O method.