Is this fibonacci?

5

2 votes
Hard
Problem

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(x1)+f(x2)+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

  • The first and only line contains an integer x.

Output Format

  • Output f(x) modulo 109 + 7.

Constraints

1x1018 (Don't get disheartened, you will get some points for brute force, but try to get 100 points! :) )

 

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

f(2) = 0 + 1 + 2 = 3

f(3) = 1 + 3 + 3 = 7

f(4) = 3 + 7 + 4 = 14

Editor Image

?