Gold Bracelet

After years of magical research, Patchouli has condensed a portion of her boundless magic into some special beads. She fills these beads only with two kinds of elemental magic: wood magic, symbolizing life and awakening, and gold magic, representing fruits and harvest. Noticing that light magic has no effect on these beads, she decides to string them together using the magical thread \(\text{Mist's Path}\) to form a bracelet.

The color of each segment of the thread is determined by the attributes of the two beads it connects. In particular, if at least one of the two beads is of gold magic, then the connecting thread becomes gold.

Patchouli wishes to create a bracelet in which every segment is gold. Given that she has an infinite supply of both types of beads, your task is to count how many ways there are to choose the beads (each bead being either wood or gold) arranged in a circle (bracelet) such that for every pair of adjacent beads (including the pair formed by the last and first beads) at least one bead is gold.

Let a bracelet consist of \(n\) beads arranged in a circle. Represent a gold bead as 1 and a wood bead as 0. Then the condition is that for every adjacent pair \((a,b)\) we have \(a + b \ge 1\). It can be shown that the total number of valid bracelets is given by:

[ A(n) = F(n-1) + F(n+1) \mod 1000000007, ]

where \(F(k)\) denotes the \(k\)th Fibonacci number with initial conditions \(F(0)=0, F(1)=1\) (using zero-based indexing).

You are to output the number of valid bracelets modulo \(1000000007\).

inputFormat

The input consists of a single line containing one integer \(n\) (\(1 \le n \le 10^{9}\)), representing the number of beads in the bracelet.

outputFormat

Output a single integer, which is the number of valid bracelets modulo \(1000000007\).

sample

1

1