Ngày 23 tháng 11 năm 2024, Trường đại học Quảng Bình có tổ chức kỳ thi tin học trẻ cho các bạn học sinh trung học phổ thông giao lưu với nhau. Các bạn học sinh THCS cũng háo hức tham gia thử sức dẫu biết là lấy trứng chọi với đá. Có ~N~ học sinh tham gia kỳ thi lập trình được sắp xếp vào 1 dãy máy tính nằm trên một đường thẳng và được đánh số từ 1 đến ~N~ (bạn thứ nhất được đánh số thứ tự là 1). Trong danh sách các bạn tham gia thì số lượng bạn nữ ít hơn khá nhiều so với số lượng bạn nam. Vì thế, ban tổ chức đã không xếp 3 bạn nữ cùng ngồi 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

Input:

• Được cho bởi tệp tht.inp gồm 1 dòng duy nhất chứa số ~N~ (~1 ≤ N ≤ 64~)

Output

• Được cho bởi tệp tht.out gồm 1 dòng chứa số nguyên duy nhất là kết quả tìm được.

Example

Input

3

Output

7

Note

• Với N = 3, giả sử ký hiệu số 0 là bạn nam, số 1 là bạn nữ thì có các cách xếp hàng như sau: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0)

Scoring

• 25% test ứng với 1 ≤ N ≤ 20
• 75% test ứng với 20 < N ≤ 64