DIVFIBS2  Divisible Fibonacci Numbers
The Fibonacci sequence is defined by : f_{n} = n for n < 2, and f_{n} = f_{n1} + f_{n2} for n > 1.
f = (0, 1, 1, 2, 3, 5, 8, ...)
You have to count how many terms are divisible by a given integer in the beginning of the sequence.
Input
The first line of input contains one integer:
T the number of test cases.
On each of the next T lines, your are given
three integers: a, b, and k.
Output
For each test case, you have to print the number of term f_{n} that are divisible by k, for n in [0..a^{b}].
As the result may be a big number, simply output your result modulo 10^{9}+7
Example
Input: 3 3 2 3 2 3 8 9 1 6 Output: 3 2 1
Explanation: For the first case, a^{b} = 3^{2} = 9, and the terms with rank 0 to 9 are : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.
There are 3 numbers divisible by k=3.
Constraints
0 < T < 10^4 0 < a < 10^18 0 < b < 10^18 1 < k < 10^18
To give more interest in the best part of the problem,
you can assume that the maximum prime factor of k is less than or equal to 10^{6}.
Time limit is approx 4x the time for my 1.4kB PY3.4 submission (based on my old code for problem ??? you should find).
Good luck, and have fun ;)
Edit(20170211) : New time limit (after compiler changes).
hide comments
[Lakshman]:
20160805 13:05:29
Last edit: 20160806 07:03:54 

[Lakshman]:
20160730 11:03:33
@Francky can you Please tell me if my approach is correct ?

Added by:  Francky 
Date:  20160716 
Time limit:  1s15s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  DIVFIBS 