{"trustable":true,"sections":[{"title":"Background","value":{"format":"MD","content":"A stack is a classic data structure in computer science. Simply put, a stack is a linear list that restricts insert and delete operations to one end.\n\nThere are two most important operations for a stack: pop (to remove an element from the top of the stack) and push (to add an element to the top of the stack).\n\nThe importance of stacks is self-evident, and any course on data structures will introduce stacks. During his review of the basic concepts of stacks, Ning Ning thought of a question that was not covered in the book, and he could not provide an answer himself, so he needs your help."}},{"title":"Description","value":{"format":"MD","content":"![](CDN_BASE_URL/d5528e831287def44cbc0333c8ef447a?v\u003d1724931408)\n\nNing Ning is considering the following problem: a sequence of operands, $1,2,\\ldots ,n$ (illustrated for the case of 1 to 3), where the depth of stack A is greater than $n$.\n\nNow, two operations can be performed:\n\n1. Move a number from the head of the operand sequence to the head of the stack (corresponding to the push operation of the data structure stack).\n2. Move a number from the head of the stack to the tail of the output sequence (corresponding to the pop operation of the data structure stack).\n\nUsing these two operations, a series of output sequences can be obtained from a sequence of operands. The following figure shows the process of generating the sequence `2 3 1` from `1 2 3`.\n\n![](CDN_BASE_URL/3c5487645837c35de1c9bbc7a6ee7ab4?v\u003d1724931408)\n\n(The initial state is shown in the above figure.)\n\nYour program will calculate and output the total number of possible output sequences that can be obtained from the operand sequence $1,2,\\ldots,n$ after performing operations."}},{"title":"Input","value":{"format":"MD","content":"The input file contains only one integer $n$ ($1 \\leq n \\leq 18$)."}},{"title":"Output","value":{"format":"MD","content":"The output file contains only one line, which is the total number of possible output sequences."}},{"title":"Sample 1","value":{"format":"MD","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\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Hint","value":{"format":"MD","content":"**【Source of the Problem】**\n\nNOIP 2003 Popular Group Problem 3"}}]}