描述

一列火车n节车厢,依次编号为1,2,3,…,n。每节车厢有两种运动方式,进栈与出栈,问n节车厢出栈的可能排列方式有多少种。

输入格式

一个数,n(n<=60000)

输出格式

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

样例输入1

3

样例输出1

5

样例输入2

50

样例输出2

1978261657756160653623774456