Flower Planting Arrangement

You are given an integer n representing the number of trees. Your task is to determine the number of distinct ways to plant flowers around the trees following these rules:

• No two consecutive trees should have flowers.
• An arrangement is valid even if no tree has a flower.

It can be shown that the number of valid arrangements is equal to $$F(n+2)$$, where the Fibonacci sequence is defined by $$F(1)=1,\ F(2)=1$$, and for \( k\geq 3 \), \( F(k)=F(k-1)+F(k-2) \). In this problem, you are required to output the answer modulo $$10^9+7$$.

For example, when n = 3, the answer is 5.

inputFormat

The input consists of a single integer n (0 \(\leq n \leq 10^{18}), which represents the number of trees.

outputFormat

Output a single integer: the number of valid arrangements modulo $$10^9+7$$.

0

1