Stair Ways

Statement

You climb a staircase with n steps, taking 1 or 2 steps at a time. Count the number of different ways to reach the top, modulo 1000000007.

Input

One integer n.

Output

Print the number of ways modulo 1000000007.

Constraints

1 <= n <= 100000

Example 1

5

8

The counts for n = 1..5 are 1, 2, 3, 5, 8.