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