DUTUYEN

Đội tuyển tin Tổng Hợp khóa abc muốn chụp lại một kiểu ảnh để làm kỉ niệm . Vào khóa abc đội  có n(n <= 10^5) thành viên.Ta giả sử chiều cao của các thành viên phân biệt . Ngoài ra họ muốn bức ảnh phải đẹp và ngay ngắn nên đi từ trái qua phải không tồn tại ba người ( không nhất thiết liên tiếp ) có chiều cao lần lượt là : trung bình , cao , thấp.
Ví dụ đội tuyển tin 2014 thì kiểu chụp :
(Đm Hiếu , Chu Hiếu , a Kiên , a Hạnh , Duy , a Sơn , DAV , Minh 11 , Minh 10 , a Dũng , Hùng , a Khánh , Hoàn) là không thỏa mãn vì bộ ba a Hạnh , Minh 11 , a Khánh có chiều cao lần lượt là trung bình , cao , thấp.  
Đội tuyển tin khóa abc phân vân xem  có bao nhiêu cách sắp xếp các thành viên để tạo ra một bức ảnh đẹp.Bạn hãy tìm số cách và in ra đáp số sau khi lấy phần dư cho 10^9 + 7.

Input

Gồm một dòng là số n ( n <= 10^5)
Có 20% số test có n <= 10

Có 40% số test có n <= 2000 

Output

Gồm một dòng duy nhất là kết quả bài toán.

Example

Input:
1

Output:
1