SPATTERN  Subset Pattern
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 nth 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 nth positon 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.
hide comments
rezwanarefin:
20160513 20:56:49
This was my first problem in SPOJ.... Newbie as a Problem Setter... So... Sorry.... 

Vipul Srivastava:
20160513 20:53:23
Now its AC 

rezwanarefin:
20160513 20:52:01
Sorry.... There was a bug in my testcase generator program...... Sorry........ :( :'( Fixed now... 

Vipul Srivastava:
20160513 20:44:02
I think this problem should be removed or at least rectified. 

The next big thing:
20160513 20:23:56
First of all, the same problem already exists  http://www.spoj.com/problems/INCPOWK/, and a little harder but based on the same concept  http://www.spoj.com/problems/TREENUM2/


SnowFire:
20160513 11:46:55
I think there is something wrong with the problem or the test data.. 10^7 + 9 isn't even prime 

rezwanarefin:
20160513 10:59:19
@fsshakkhor 1. Suppose you have number x^0, x^1, x^2 .... The array is formed by taking 0,1,2... elements at a time and sum then up. so when you take 0 numbers then the sum is always 0. 

rezwanarefin:
20160513 10:57:02
When x = 0 then the array should be {0,0,0,0,0,0,0,0,.......} Why only one element? 

fsshakkhor:
20160513 09:11:07
Clarification Needed

Added by:  Rezwan 
Date:  20160512 
Time limit:  0.5s 
Source limit:  2000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 