""Tùng...Tùng...Tùng"", tiếng trống báo hiệu đã đến giờ vào lớp, các bạn học sinh bắt đầu xếp hàng để chuẩn bị vào lớp. Lúc đó, bạn Khiêm vô tình nhìn thấy bạn Thảo cùng bạn Linh đang đứng kề nhau nói chuyện rôm rã. Là tổ trưởng, Khiêm không thể đứng nhìn các bạn nói chuyện mất trật tự như thế, vì vậy cậu cố sắp xếp các bạn trong hàng của mình sao cho không có các bạn nữ nào đứng kề nhau. 
Yêu cầu: Khiêm có thể thay đổi số lượng thành viên nam hoặc nữ trong tổ, nhưng vẫn giữ nguyên là N thành viên, hãy tính xem Khiêm có bao nhiêu cách để sắp xếp thỏa mãn.

Input: Nhập từ bán phím số nguyên dương N (N≤10⁵).

Output: In ra màn hình một số nguyên dương là số cách sau khi đã chia lấy dư cho 10⁹+7.

Ví dụ

Input

3

Output

5

Giải thích ví dụ

• Có 5 trường hợp thỏa mãn là FMF, FMM, MFM, MMF, MMM. (Nam là M, nữ là F)