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 109 + 7.
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.
OutputFor each test case, output a single integer denoting the number of easy numbers in base b consisting of d digits, modulo 109 + 7.
- 1 ≤ T ≤ 100
- 2 ≤ b ≤ 16
- 1 ≤ d ≤ 109
Input: 2 2 2 10 3 Output: 1 150
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.
|Tags||backtracking, cook70, easy, enumeration, pdn, precomputation, wwwwodddd|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.