On the land of Mordor, the Dark Lord Sauron has made a rule about how the houses of the orcs should be constructed. There are two types of houses: a single-house (which is n units in length) and a double-house (which is 2n units in length having a separating wall between its constituent houses). All the houses are to have a fixed width so they can be placed next to each other. The architect of Mordor, Saruman, wants to know the number of ways k houses can be constructed in a row. Note: A double-house, though appears like an individual house, is actually two houses.

INPUT:

A single positive integer k such that 1 <= k <= 100

OUTPUT:

A single integer s which is the number of ways of having such a construction. Since the output can be very large, output the answer s modulo (10^9 + 7).

Sample Testcase #1:

Input:

3

Output:

3

Explanation:

Way 1: All 3 single-houses ( [] [] [] )

Way 2: One single-house followed by one double-house ( [] [[]] )

Way 3: One double-house followed by one single-house ( [[]] [] )

Sample Test #2:

Input:

2

Output:

2

Explanation:

Way 1: Both single-houses ( [] [] )

Way 2: One double-house ( [[]] )