{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eGiven 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.\u003c/p\u003e\u003cp align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/0e398990d8634add45432ed4d65a3ef9?v\u003d1726073919\"\u003e\u003c/p\u003e\u003cp align\u003d\"center\"\u003eFigure 4: Divisions of a regular pentagon into triangles and quadrangles\u003c/p\u003e\u003cp\u003eGiven \u003ci\u003en\u003c/i\u003e, the number of sides of the polygon, compute the number of such divisions.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input contains multiple test cases. Each test case consists of a single integer \u003ci\u003en\u003c/i\u003e (3 ≤ \u003ci\u003en\u003c/i\u003e ≤ 5000) on a separate line. The input ends where EOF is met.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, print the answer modulo 2\u003csup\u003e64\u003c/sup\u003e on a separate line.\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n4\r\n5\r\n6\r\n7\r\n8\r\n9\r\n10\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n3\r\n10\r\n38\r\n154\r\n654\r\n2871\r\n12925\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}