For some number X, let \(F(X)\) denote the total number of sequences having length ≤ K such that bitwise OR of all the elements in a sequence is equal to X.

For a given N , K and prime p, calculate the value of \( \sum_{i=0}^{N} \) \(p^{i}\) * \(F(i)\).

Input:
Input will consists of several test cases.
First line of input will consists of a single integer T denoting the number of test cases. Each of the next T lines consist of integers N , K and p separated by a single space.

Output:
For each test case, output \( \sum_{i=0}^{N} \) \(p^{i}\) * \(F(i)\). Since, the value can be large, output the value modulo \(10^{9} + 7\).

Constraints:

\(1 ≤ T ≤ 10^{4}\)
\(0 ≤ N < 2^{32}\)
\(1 ≤ K ≤ 10^{6}\)
\(2 ≤ p < 10^{6}\) where p is a prime number.