Description

给定1～N这N个整数和一个无限大的栈，每个数都要进栈并出栈一次。如果进栈的顺序为1，2，3...N（即i没进过栈时，i+1不能进栈），那么出栈的可能排列方式有多少种？

例如：3个整数时：

方案一：1进1出2进2出3进3出，出栈序列：123

方案二：1进1出2进3进3出2出，出栈序列：132

方案三：1进2进2出3进3出1出，出栈序列：231

方案四：1进2进2出1出3进3出，出栈序列：213

方案五：1进2进3进3出2出1出，出栈序列：321

Input Format

一个数，n(n<=60000)## Output Format

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

3​

5