I wanted to give you guys a nice fibonacci expression, but unfortunately my computer got attacked and the expression got changed to this:
f(x)=f(x−1)+f(x−2)+x
Even worse, my keyboard broke down too so i can't even change this expression. :(
The only thing i remember is f(0) = 0 and f(1) = 1.
But this won't stop you guys right? Output f(x) modulo 109 + 7.
Input Format
Output Format
Constraints
1≤x≤1018 (Don't get disheartened, you will get some points for brute force, but try to get 100 points! :) )
f(2) = 0 + 1 + 2 = 3
f(3) = 1 + 3 + 3 = 7
f(4) = 3 + 7 + 4 = 14