Description
After some hard work of finding his queen, Knuckles finally arrived NTHU!
Knuckles is exhausted. He wants to grab some delicious food. However, as all of us know......
THERE IS NO "DELICIOUS" FOOD IN HSINCHU.
(Actually there are some restaurants that are not bad. But just "not bad"...)
This truth, which is cruel, hits Knuckles pretty hard. Knuckles doesn't give up and start his journey of finding delicious food in Hsinchu.
However, the more he goes out and seeks, the truth is just getting more clear...
The i-th time that those bad-taste restaurants Knuckles found is Fi . Knuckles found that F1 = 1, F2 = 1, and Fi = Fi-1 + Fi-2 .
The more Knuckles goes out, the more bad-taste restaurants he found.
He is tired of finding more and more bad restaurants. He just wants to know there are how many bad restaurants when he goes out for the i-th time.
- There's a sequence F.
- F1 = 1, F2 = 1, Fi = Fi-1 + Fi-2.
- Find out Fi .
Hint：
Input
The input contains multiple lines, ended by EOF.
Every line contains an integer i.
1 <= i <= 1018.
There will be at most 20 lines.
Output
Output Fi.
Because Fi might be too big, the answer should mod 109+7, which means you should output Fi % (109+7).
Remember to print a '\n' at the end of the output.