題目描述

现在有一个准备入栈的队列：1,2,3,...,n

入栈队列的顺序是：1,2,3,...,n

你可以进行两种操作

1.将即将入栈的队列放进栈中(相当于push)

2.将栈中最后一个数放进出栈队列的最后方(相当于pop)

请问最后出栈队列中的n个数可以有多少排列的方式

例如n=3时，其中一个出列的方式是2,3,1

入栈队列：1,2,3 , 栈：None , 出栈队列：None

1.入栈队列：2,3 , 栈：1 , 出栈队列：None

2.入栈队列：3 , 栈：1,2 , 出栈队列：None

3.入栈队列：3 , 栈：1 , 出栈队列：2

4.入栈队列：None , 栈：1,3 , 出栈队列：2

5.入栈队列：None , 栈：1 , 出栈队列：2,3

6.入栈队列：None , 栈：None , 出栈队列：2,3,1

輸入格式

一个正整数n(1<=n<=18)

输出最后出栈队列中的n个数可以有多少排列的方式

["3","4","5"]

["5","14","42"]