Bài tập

Thám tử K cho phép chuỗi nhị phân có cặp \(00\) xuất hiện, nhưng chỉ không quá 2 lần. Hãy sử dụng đệ quy để liệt kê tất cả các chuỗi nhị phân có độ dài \(N\) thỏa mãn ràng buộc về số lần xuất hiện của cặp "00".

Input

Một số nguyên dương \(N\) (\(1 \leq N \leq 15\)).

Output

In ra số lượng chuỗi nhị phân thỏa mãn điều kiện.

Example

1

2

2

4

3

8

4

15

Xây dựng hàm giaithua(n) để tính giai thừa của một số nguyên không âm \(n\). Giá trị trả về là \(n!\). Áp dụng hàm đã xây dựng để tính và in ra \(n!\) với \(n\) được nhập từ bàn phím.

\(n! = 1 \times 2 \times 3 \times \dots \times n\).

Input

• Một số nguyên không âm \(n\) (\(0 \leq n \leq 15\)).

Output

Một dòng duy nhất chứa giá trị của \(n!\).

Example

3

3! = 6

Trong các giờ giải lao, Nam và Lan rất hay nhắn tin cho nhau bằng cách viết tin nhắn vào một mẫu giấy và nhờ các bạn chuyển giúp mẫu giấy đó đến người nhận. Tất nhiên cách truyền tin này là không bảo mật do các bạn khác có thể dễ dàng đọc được nội dung tin nhắn. Nam rất thông minh, cậu đã nghĩ ra một cách mã hóa tin nhắn. Nam chọn một số nguyên \(k\) và thay mỗi chữ cái trong tin nhắn bằng chữ cái đứng sau chữ đó \(k\) vị trí ở bảng chữ cái, nếu là ký tự trắng thì giữ nguyên.
Trong các tin nhắn này ta chỉ quan tâm đến các chữ cái Tiếng Anh in hoa từ A đến Z và có thể coi bảng chữ cái có tính chất tuần hoàn, chữ đứng sau Z một vị trí là A, sau Z hai vị trí là B,...

Ví dụ với giá trị \(k=2\) và nội dung tin nhắn đã mã hóa là CDEZAB thì nội dung tin nhắn gốc là ABCXYZ. Lan biết giá trị \(k\) nhưng việc giải mã đối với Lan tốn rất nhiều thời gian.

Yêu cầu: Với giá trị \(k\) và nội dung tin nhắn đã mã hóa. Hãy viết chương trình giúp Lan giải mã tin nhắn của Nam.

Input

• Dòng thứ nhất chứa giá trị \(k\) (\(1 ≤ k ≤ 26\));

• Dòng thứ hai chứa một xâu khác rỗng gồm các ký tự trắng và các chữ cái Tiếng Anh in hoa là tin nhắn đã mã hóa. Độ dài xâu không quá 100 ký tự.

Output

Gồm 1 dòng là tin nhắn sau khi được giải mã

Example

2
FK CP EJG

DI AN CHE

Mùa noel sắp tới, ông già Noel đang chuẩn bị phát quà cho các bạn nhỏ. Ông già Noel sẽ phát quà theo quy tắc sau :

• Bạn nhỏ đầu tiên sẽ nhận đúng \(1\) phần quà.
• Bạn nhỏ thứ hai nhận đúng \(4\) phần quà.
• Bạn nhỏ thứ ba nhận đúng \(7\) phần quà.
• Bạn nhỏ thứ bốn nhận đúng \(10\) phần quà.
• Cứ như vậy, bạn nhỏ đứng sau sẽ nhận nhiều hơn bạn phía trước đúng \(3\) phần quà.

Có \(N\) bạn nhỏ sẽ đến nhận quà. Vậy ông gia Noel phải chuẩn bị bao nhiêu phần quà để phát cho tất cả \(N\) bạn ?

Input

Nhập vào một số nguyên dương \(N\). \((N \leq 10000)\)

Output

Tổng số phần quà theo đề bài.

Example

1

1

2

5

3

12