Có một chiếc cầu thang thần kỳ với N bậc. Mỗi lần bước, người ta có thể đi lên một bậc hoặc hai bậc. Câu đố đặt ra là: có bao nhiêu cách khác nhau để đi từ dưới đất lên tới bậc thứ N?

Bin muốn thử tất cả các cách đi khác nhau để tìm ra cách "đẹp nhất", nhưng số cách là quá lớn. Vì vậy Bin chỉ cần biết số cách (chia lấy dư cho 10^9 + 7) để lên đến bậc thứ N.

Yêu cầu

Cho số nguyên dương N. Hãy tính số cách đi từ bậc 0 lên bậc N, biết mỗi bước đi được 1 hoặc 2 bậc. In kết quả chia lấy dư cho 10^9 + 7.

Dữ liệu vào

Đọc từ file STAIR.INP:

• Gồm một dòng duy nhất chứa số nguyên N (1 ≤ N ≤ 10^6).

Dữ liệu ra

Ghi ra file STAIR.OUT:

• Một số nguyên duy nhất là số cách lên tới bậc N, lấy modulo 10^9 + 7.

Ví dụ

Ví dụ 1:

Giải thích: Chỉ có 1 cách: bước 1 bậc.

Ví dụ 2:

Giải thích: Cách 1: 1 + 1; cách 2: bước 2 bậc một lần.

Ví dụ 3:

Giải thích: 1+1+1; 1+2; 2+1.

Subtask

• Subtask 1 (40% số điểm): 1 ≤ N ≤ 30.
• Subtask 2 (60% số điểm): 1 ≤ N ≤ 10^6.