The Colors of Corruption

All submissions for this problem are available.
In a vacancy of three positions where the probablity of person in the front is the greatest to qualify, an intresting bribe scandal occurred. The first person,P1 managed to get first slots by bribing Rs B to his connection, the second, P2 payed the first person equal bribe, B to let him in the first position and first goes second. The third, P3 agrees to pay both P1 and P2, the amount they payed in bribe, hence position is now P3 P2 P1. Then the three arrive at a conclusion, for any new person coming for the front position, he has to pay bribe to front three positions, the amount they payed at their entry.
Given the amount B, you need to find the bribe payed by the Nth briber.
Problem Setter: Shahzor Khan
Input
First line gives the number of test cases,T(0<=T<=10000), followed by T lines.Each test case contain 2 integers B and N(described in the problem) seperated by a space.
(0<=B<=1000)
(0<=N<=1,000,000,000,000)
Output
For each case, print the amount of bribe payed by Nth briber mod 10000007.
Example
Input: 5 1 0 1 1 1 2 1 3 1 4 Output: 0 1 1 2 4
Author:  ganesha 
Tags  ganesha 
Date Added:  13042011 
Time Limit:  0.385475 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 