暂无测试数据。

题目描述

按照 \(1,2,\cdots,n-1,n\) 的顺序入栈，
问可以得到多少种出栈序列。

如 \(n=3\) 时, 有 1 2 3，1 3 2，2 1 3，2 3 1，3 2 1 共5种出栈序列。

输入

一个正整数 \(n\),表示数的个数。

输出

输出一个数表示出栈序列的种数。

样例输入

3

样例输出

5

数据范围限制

\(1 \leq n \leq 30\)

来源

CCF基础篇补充8.5