题目描述

一列火车 n 节车厢，依次编号为 1,2,3,…,n。

每节车厢有两种运动方式，进栈与出栈，问 n 节车厢出栈的可能排列方式有多少种。

输入格式

输入一个整数 n，代表火车的车厢数。

输出格式

输出一个整数 s 表示 n 节车厢出栈的可能排列方式数量。

样例

3

5

数据范围

• $1≤n≤60000$

来源

• 算法竞赛进阶指南