Nhân dịp kết thúc năm học, trường THCS ABC có tổ chức cho các em học sinh giao lưu với nhau, có nhiều trò chơi được ban tổ chức đưa ra đê các em cùng tham gia. Có ~ n ~ học sinh tham gia trò chơi được xếp hàng thành một đường thẳng và được đánh số thứ tự từ 1 đến ~ n ~ (em thứ nhất được đánh số thứ tự là 1). Trong danh sách các em tham gia thì số lượng bạn nam ít hơn khá nhiều so với số lượng bạn nữ. Vì thế, ban tổ chức đã không xếp 3 bạn nam cùng đứng kề nhau.

Yêu cầu: Hãy cho biết có bao nhiêu cách xếp hàng thỏa mãn điều kiện trên.

Dữ liệu vào:

• Số nguyên dương ~ n ~

Kết quả:

• Ghi một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

Input

3 

Output

7 

Giải thích: Với ~ n=3 ~, giả sử ký hiệu số 0 là bạn nữ, số 1 là bạn nam thì có các cách xếp hàng như sau: ~000; 001; 010; 011; 100; 101; 110~

Ràng buộc:

• 25% test ứng với ~ 1<n≤20 ~;
• 75% test ứng với ~ 20<n≤64 ~.