Flag consists of n vertical stripes of white, red and blue. Neighbouring stripes cannot have the same color, and the blue strip should always be between red and white. In how many ways can we color a flag with n stripes?

Input

Number of strips n (1 ≤ n ≤ 106) on the flag.

Output

Print the number of ways to color the flag with n stripes. Print he answer modulo 109 + 7.