Killjee and Magic Value
Practice
3.4 (13 votes)
Mathematics
Modular arithmetic
Easy Medium
Problem
18% Success 5099 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

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

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
21 votes
Tags:
SortingIntegerModulus ArithmeticModulesC++Number TheoryMathematics
Points:30
3 votes
Tags:
MathematicsModular arithmeticEasy-Medium
Points:30
5 votes
Tags:
Easy-Medium