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 sắp xếp thành một hàng đườ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.

Input

• Gồm số ~N~ (~1 \leq N \leq 64~).

Output

• Một số nguyên duy nhất là kết quả tìm được.

Giới hạn

• 25% test ứng với ~1 \leq N \leq 20~.
• 75% test ứng với ~20 < N \leq 64~.

Example Test

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:

~(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0)~.