求出栈序列个数

题目描述:

求出栈序列个数

现在有一个栈，以1，2，3，…，n作为入栈序列，求可能的出栈序列个数。

输入格式:

 输入n

输出格式:

 输出出栈序列个数

样例输入:

4

样例输出:

14

提示:

样例解释

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
3 2 1 4
3 2 4 1
3 4 2 1
4 3 2 1

 n<=18

时间限制: 1000ms
空间限制: 256MB

---

来源: NOIP2003普及T3