Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Polygon Division
Time Limit: 2000MSMemory Limit: 131072K
Total Submissions: 1367Accepted: 735

Description

Given a regular polygon, there are numerous ways to divide it into several triangles and/or quadrangles by adding some diagonals that do not properly intersect each other. For example, Figure 4 shows all ten different divisions of a regular pentagon into triangles and quadrangles.

Figure 4: Divisions of a regular pentagon into triangles and quadrangles

Given n, the number of sides of the polygon, compute the number of such divisions.

Input

The input contains multiple test cases. Each test case consists of a single integer n (3 ≤ n ≤ 5000) on a separate line. The input ends where EOF is met.

Output

For each test case, print the answer modulo 264 on a separate line.

Sample Input

3
4
5
6
7
8
9
10

Sample Output

1
3
10
38
154
654
2871
12925

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator