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ố 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 đầu vào

• Gồm số \(N\) \((1 \le N \le 64)\)

Dữ liệu ra

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

Scoring

• \(25\)% test ứng với \(1 \le N \le 20\)
• \(75\)% test ứng với \(20 \lt N \le 64\)

Input 1

3

Output 1

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)