小虎刚刚上了幼儿园，老师让他做一个家庭作业：首先画3行格子，第一行有三个格子，第二行有2个格子，第三行有1个格子。每行的格子从左到右可以放棋子，但要求除第一行外，每行放的棋子数不能超过上一行的棋子。玩了一会儿，小虎的哥哥大虎：这个作业有很多种摆放法，我想找到，但我不知道有多少种方案，你能帮助我吗？
大虎是学校信息学集训队的，立刻想到用计算机来解决这个问题，并很快有了解答：13.
第二天他把问题拿到学校，并说如果第一行有N个格子，第二行有N-1个格子，…，第N行有1个格子，怎么办？现在请你一块来帮助他解决这个难题。
数据范围
30%数据：1<=n<=12
50%数据：1<=n<=30
100%数据：1<=n<=100

仅一行，一个正整数N。

一行，方案总数。

【样例1说明】 O表示有棋子，X表示没有棋子

OX OO OX OO

X X O O

题目要求必须放一个及一个以上的棋子，即棋盘不能为空