Có ~n~ bậc thang. Mỗi lần, Nam có thể bước ~1~ bậc hoặc ~2~ bậc. Hỏi có bao nhiêu cách khác nhau để đi hết ~n~ bậc thang?

Yêu cầu: Tính và in ra số cách để leo hết ~n~ bậc thang.

Input

Một số nguyên dương ~n~ (~n \leq 10^6~).

Output

Một số nguyên dương duy nhất là số cách để leo hết ~n~ bậc thang modulo ~10^9+7~.

Scoring

• Subtask ~1~ ~(60\%)~: ~n \leq 20~;
• Subtask ~2~ ~(40\%)~: ~n \leq 10^6~.

Example input 1

4

Example output 2

5

Note 1

• Các cách đi:
  • ~1 + 1 + 1~.
  • ~1 + 1 + 2~.
  • ~1 + 2 + 1~.
  • ~2 + 1 + 1~.
  • ~2 + 2~.

~→~ Có ~5~ cách.