圣诞节就要到了，小皮准备了n 个圣诞礼物，把它挂在一棵特别的圣诞树上。顽皮的小球发现这棵圣诞树相当地特别，它是一棵二元树，所有的礼物都挂在叶子上，而且每一个节点都可以旋转，并将整棵子树左右反过来。如下图来说，旋转了箭头所指的那个节点以后，整棵子树和所有礼物的顺序就会反过来：

小球把原本所有叶子上的礼物由左到右编号为1到n ，并且观察它们经过旋转以后的排列状况，以上图为例，小球把结果标记成(3, 2, 1, 4) ，并称呼它为一个礼物序列。顽皮的小球把这个发现告诉小皮 ，他们决定把所有n片叶子的圣诞树都找出来，把所有叶子上挂的礼物由左到右编号为1到n ，然后开始旋转节点，并将所有的礼物序列记录下来。不过由于数量实在是太多了，而且重复的礼物序列太多， 小皮和小球请你帮忙把礼物序列整理整理，并且告诉小皮和小球总共会有多少个不同的礼物序列？注意到并不是所有n元的序列都是礼物序列，例如(3, 1, 4, 2)这个序列，你找不到任何一棵圣诞树可以得到这个序列。