Henry needs to go to the washroom again. He needs to walk exactly $N$ steps to reach the washroom.

Henry flips a coin. If it lands on heads, Henry advances 3 steps. If it lands on tails, Henry advances 1 step only. He repeates this until he reaches the washroom.

Note that Henry may be one or two steps away from the washroom but, after flipping a coin, is required to advance 3 steps. In this case, Henry is unable to reach the washroom and cries.

Calculate the number of ways Henry can reach the washroom modulo $10^9 + 7$.

Input

The only line of input contains an integer $N$. $(1 \le N \le 10^6)$

Output

Output the required answer.