e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Simple Combinatorics

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 (1n106) on the flag.

Output

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

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
Output example #1
4