In this question, Killjee gives you three integers $N$, $M$, and $K$. You need to find the magic value of three numbers.

Suppose $P = \sum_{i=N}^{M}$ fibonacci[$i$]$*i!$ (factorial here), where fibonacci[$0$]$=$fibonacci[$1$]$=1$ and fibonacci[$i$] $=$ fibonacci[$i - 1$] $+$ fibonacci[$i - 2$]. The magic value is maximum X. Such that $K*X$$\le P$.

Since the answer could be very large, you only need to print the magic value $\% 10^9+7$.

INPUT FORMAT

First line of input contains a single integer $T$, number of test case. $T$ lines follow each containing three space separated integers $N,M,K$.

OUTPUT FORMAT

For each test case print a single integer, magic value of 3 numbers in new line.

INPUT CONSTRAINTS

• $1 \le N \le M \le 2*10^6$
• $1 \le K \le 10^6$
• $1 \le T \le 20$