SP27433 DIVFIBS2 - Divisible Fibonacci Numbers

The Fibonacci sequence is defined by : _f $ _{n} $_ = _n_ for _n_ < 2, and _f $ _{n} $_ = _f $ _{n-1} $_ + _f $ _{n-2} $_ 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.

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_.

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