G. *【递归】出栈方案统计[NOIP普及组2003]（视频）

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

栈是常用的一种数据结构，有 $n$ 个元素在栈左侧等待进栈，栈的右侧是出栈序列。

栈的操作有两种：push 和 pop ，前者是将左侧一个元素进栈，后者是将栈顶元素弹出到右侧。

不同的操作序列可以得到不同的输出（右侧）序列。

输出 $n$ 个元素的出栈序列方案总数。

一个整数 $n \ (1 \le n \le 18)$ 。

一个整数，即可能得到的输出序列方案总数。