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.