Trên một hành lang có $n$ tấm nệm được xếp thành một hàng. Giờ nghỉ trưa, mỗi người có thể nghỉ theo một trong ba tư thế sau:

1. Ngồi trên đúng 1 tấm nệm.
2. Nằm hướng đầu sang trái, chiếm đúng 2 tấm nệm kề nhau.
3. Nằm hướng đầu sang phải, chiếm đúng 2 tấm nệm kề nhau.

Hai người không được dùng chung một tấm nệm, và toàn bộ $n$ tấm nệm phải được dùng hết (không bỏ trống).

Yêu cầu

Hãy cho biết có bao nhiêu cách bố trí tư thế nghỉ trên dãy $n$ tấm nệm thỏa mãn tất cả điều kiện trên. Hai cách bố trí được coi là khác nhau nếu tồn tại một tấm nệm mà trong hai cách tư thế sử dụng khác nhau.

Dữ liệu

Vào từ đầu vào chuẩn một dòng duy nhất chứa số nguyên $n$.

Kết quả

Ghi ra đầu ra chuẩn một số nguyên duy nhất là số cách bố trí hợp lệ chia lấy dư cho 1000000007.

Ví dụ mẫu

2

3

Giới hạn

Subtask 1 (25%): $1 \le n \le 20$.

Subtask 2 (50%): $1 \le n \le 50$.

Subtask 3 (25%): $1 \le n \le 250000$.