beecrowd | 2953

One More Game

By Samuel Eduardo da Silva, IFSULDEMINAS/UFF BR Brazil

Timelimit: 1

Fingolfin loves board games. One day, you are faced with a very strange game called "2 First primes". Basically this game consisted of a single-row horizontal board containing N houses. The player starts at house number 1 and the goal is to get to house N (not being able to get past). In each round, the player can move in two ways: walk 2 or 3 houses forward (oh yes, now makes sense the title of the game). Fingolfin found the game very easy (only to go forward), so his colleague Fëanor challenges him to say how many different possibilities there are of him to finish the game, that is, in how many different ways Fingolfin, from the house 1, can get to the house N. Fingolfin is a bit busy taking care of some housework and asked you, given the number of houses on the board, to solve the challenge.

Input

Integer N(1 ≤ N ≤ 105), indicating the number of boxes on the board.

Output

Integer indicating the number of possibilities to end the game. The number of possibilities can be very large, so one should only show the remainder value of this value when it is divided by 109 + 7.

Input Samples Output Samples

3

1

100

505425294

23238

34135335