Climbing a Ladder

By Deyao Chen

Problem Statement

You are designing an open world game. In the game, a character can climb a ladder to move up. In each move, the character can either climb up one unit by pressing the up arrow, or leap up $3$ moves by pressing x. Note that if there is less than $3$ units left of the ladder, the player can still choose to leap.

Now you want the game to drop a loot whenever the player does a specific combination of moves and leaps (Think of this as a sort of hidden cheat code or hidden combo). Obviously, the higher the ladder, the more unlikely the player will randomly stumble across the specific combination. So you decide to count the number of combinations of moves given the height of a ladder to gauge the difficulty of achieving the hidden combo.

Constraints

$1 \le n \le 10^{15}$.

Subtask 1 (20%)

$1 \le n \le 20$.

Subtask 2 (20%)

$1 \le n \le 10^{3}$.

Subtask 3 (20%)

$1 \le n \le 10^{5}$.

Subtask 4 (40%)

No more constraints.

Input

Input one number, $n$, the height of the ladder.

Output

Output one number, $a$, the remainder of the number of combinations of moves divided by $10^{9} + 7$.

Examples

5

9