时间限制：1秒　　内存限制：256M

---

【问题描述】

　　定一个深度为 \(n\) 的栈，有 \(n\) 个元素，按 \(1,2,,…,n\) 的顺序进栈，请问有多少种不同的出栈序列？

【输入格式】

　　一个正整数 \(n\)，表示进栈序列 \(1,2,,…,n\)。

【输出格式】

　　一个整数，表示不同的出栈序列总数。

【输入输出样例】

　Input

3

　Output

5

【样例说明】

　　按1,2,3进栈，可能有下面五种出栈序列：
　　　1,2,3
　　　1,3,2
　　　2,1,3
　　　2,3,1
　　　3,2,1

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤n≤19\)。

【来源】

　　Mr.he