Có một con ếch ở bậc ~0~ muốn lên bậc ~n~. Mỗi lần ếch có thể nhảy ~1~ hoặc ~2~ bậc.

Hãy tính số cách khác nhau để ếch lên đúng bậc ~n~

Kết quả có thể rất lớn nên chỉ cần in ra phần dư sau khi chia cho ~10^9+7~

Input

• Một số nguyên ~n~ trong đó ~0 \le n \le 10^7~

Output

• Số cách ~\text{mod } 10^9+7~.

Ví dụ

Input

4

Output

5