Easy Numbers

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
While studying representation of numbers in various bases, Chef discovered an interesting properties of some positive numbers, which Chef believed are somewhat easy to memorize. Chef called such positive numbers easy numbers.
These numbers had an interesting property: Let the base Chef is currently studying be b. Represent the number in base b (without leading zeros). For each prefix of length k (from 1 to number of digits in number in the base), the number formed by considering the digits of the prefix in base b is divisible by k.
For example, let base Chef is studying be 2.
 1 is an easy number as its prefix of length 1 (i.e. 1) is divisible by 1.
 2 is also an easy number, as its prefix of length 1 (i.e. 1) is divisible by 1 and the prefix of length 2 (i.e. 2, represented as 10 in base 2) is also divisible by 2.
 3 is not an easy number, as its prefix of length 2 (i.e. 3, represented as 11 in base 2) is not divisible by 2.
Now Chef finds these numbers easy and thinks that following question related to easy numbers will be easy for you too. He asks you to find the number of easy numbers represented in base b and consisting of exactly d digits. As the answer could be quite large, output it modulo 10^{9} + 7.
Input
First line of the input contains a single integer T denoting the number of test cases.
For each test case, there will be a single line containing two space separated integers b, d, denoting the base and number of digits respectively.
Output
For each test case, output a single integer denoting the number of easy numbers in base b consisting of d digits, modulo 10^{9} + 7.Constraints
 1 ≤ T ≤ 100
 2 ≤ b ≤ 16
 1 ≤ d ≤ 10^{9}
Example
Input: 2 2 2 10 3 Output: 1 150
Explanation
Example case 1. There are 2 numbers in base 2 consisting of 2 digits. Those are 2 (represented as 10 in base 2) and 3 (represented as 11 in base 2). 2 is an easy number, whereas 3 is not (see the explanation about it in the problem statement). Hence the number of easy numbers consisting of 2 digits in base 2 are 1.
Author:  wwwwodddd 
Tester:  kevinsogo 
Editorial  http://discuss.codechef.com/problems/EZNO 
Tags  backtracking, cook70, easy, enumeration, pdn, precomputation, wwwwodddd 
Date Added:  14052016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, 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. 