Problems
Flags
Flags
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.
Input example #1
3
Output example #1
4