SPOJ.com - Problem SPATTERN

SPATTERN - Subset Pattern

#combinatorics #bitmasks

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.

Submit solution!

hide comments



	rezwanarefin: 2016-05-13 20:56:49 This was my first problem in SPOJ.... Newbie as a Problem Setter... So... Sorry....
	Vipul Srivastava: 2016-05-13 20:53:23 Now its AC
	rezwanarefin: 2016-05-13 20:52:01 Sorry.... There was a bug in my testcase generator program...... Sorry........ :( :'( Fixed now...
	Vipul Srivastava: 2016-05-13 20:44:02 I think this problem should be removed or at least rectified.
	The next big thing: 2016-05-13 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/ Second, there is probably something wrong with the test data...i've tried a couple of different possibilities with x=1, both gave me WA. Last edit: 2016-05-13 20:25:40
	SnowFire: 2016-05-13 11:46:55 I think there is something wrong with the problem or the test data.. 10^7 + 9 isn't even prime
	rezwanarefin: 2016-05-13 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: 2016-05-13 10:57:02 When x = 0 then the array should be {0,0,0,0,0,0,0,0,.......} Why only one element?
	fsshakkhor: 2016-05-13 09:11:07 Clarification Needed- 1. 0 can not be written as the power of a base or the sum of powers of a base ; when the base is greater than 0. So by default, is the number at the 0th index always 0 ? 2. When x=0, there will be only one number in the array. Then is it obvious that n will not be greater than 0 ? Last edit: 2016-05-13 09:12:06

Submit solution!

Added by:	Rezwan
Date:	2016-05-12
Time limit:	0.5s
Source limit:	2000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 GOSU JS-MONKEY