Calculations
Practice
0 (0 votes)
Integer factorization
Basics of implementation
Implementation
Mathematics
Math
Number theory
Problem
93% Success 615 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code
You are given the following recurrent formula:
\(T_n = T_{n - 1} + T_{n - 2} + T_{n – 3}\) , at \(n > 3\), \(T_1 = 3, T_2 = 2, T_3 = 1\)
Calculate the following value, \( S = (T^2_1 + T^2_2 + ... + T^2_N ) mod (10^9 + 7)\).
Input format
The first line contains one integer \(N\).
Output format
Print \(S\) denoting the answer to the problem.
Constraints
\(1 ⩽ N ⩽ 10^{18}\)
Sample Input
8
Sample Output
4484
Explanation
t[1] = 3
t[2] = 2
t[3] = 1
t[4] = 6
t[5] = 9
t[6] = 16
t[7] = 31
t[8] = 56
S = (3^2+2^2+1^2+6^2+9^2+16^2+31^2+56^2) mod (1e9+7)=4484
Code Editor
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
Submissions
Please login to view your submissions
Similar Problems
Points:50
Tags:
Hard
Points:50
Tags:
HardRecruitNumber TheoryReadyGrammar-VerifiedMathematicsSimulationApprovedFactorization
Points:50
1 votes
Tags:
MathematicsSieveHardNumber TheoryFactorization
Editorial
Login to unlock the editorial
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