P5879 放棋子

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

仅一行，一个正整数 $N$。

一行，方案总数。

样例 1 说明：$N=2$ 时，有如下 $4$ 种摆放棋子法（`*` 表示棋子，`_` 表示空格）： | 方案数| 1 | 2 | 3 | 4 | | :----------- | :----------- | :----------- | :----------- | :----------- | | **第一行** | `*_` | `**` | `*_` | `**` | | **第二行** | `_` | `_` | `*` | `*` | 对于 $30\%$ 数据：$1\le N\le 12$。 对于 $50\%$ 数据：$1\le N\le 30$。 对于 $100\%$ 数据：$1\le N\le 100$。