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$$