Calculations
88% Success509 Attempts50 Points1s Time Limit256MB Memory1024 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}\)
Examples
Input
8
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
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 Editor...
Results