Almost Fibonacci
Submit solution
Points:
3 (partial)
Time limit:
1.0s
Memory limit:
977M
Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
A sequence \((u)\) is defined as follows:
\(u_0 = 0\)
\(u_1 = 1\)
\(u_n = u_{n - 1} + u_{n - 2} + 1\) for all \(n \ge 2\).
Given integer \(n\), find the value of \(u_n\) modulo \(10^9 + 7\).
Input
A single integer \(n\).
Note: Use \(64\)bit integer to input number.
Output
A single integer.
Constraints
Subtask \(1\) \((30\%)\): \(0 \le n \le 20\).
Subtask \(2\) \((30\%)\): \(0 \le n \le 10^6\).
Subtask \(3\) \((40\%)\): \(0 \le n \le 9*10^{18}\).
Example
Input:
4Output:
7
Comments