照片由 Wikimedia Commons 用户 Rauenstein 提供

上周末，你和你的朋友们去参观了当地城镇广场的农贸市场。当你们围成一圈聊天时，你无意中听到两个朋友在琢磨一个听起来很有趣的问题：他们正在思考所有人同时两两握手，且没有任何人的手臂相交的握手方案数。

思考了几秒钟后，你决定加入这两个朋友，并与他们分享这个问题的解决方案。“如果我们有 $2n$ 个人，”你说，“任选一个特定的人，让他与某个人握手。这个人必须在与他握手的人的两侧各留下偶数个别的人。在剩下的 $n - 1$ 对人中，他可以在右侧留下 $0$ 对、左侧留下 $n - 1$ 对，或者右侧留下 $1$ 对、左侧留下 $n - 2$ 对，依此类推。左右两侧剩余的人可以独立地选择任何可能的无交叉握手方式，因此 $n$ 对人的握手方案数 $C_n$ 为：”

$$C_n = C_{n-1}C_0 + C_{n-2}C_1 + \dots + C_1C_{n-2} + C_0C_{n-1}$$

“这与 $C_0 = C_1 = 1$ 一起，恰好就是卡特兰数（Catalan numbers）的定义。”通过查阅你手边实用的组合数学书，你发现有一个更高效的公式来计算 $C_n$，即：

$$C_n = \frac{\binom{2n}{n}}{n + 1}$$

在大家集体发出一声叹息后，你那特别爱开玩笑的朋友 Val 喊道：“既然我们在城镇广场（town square，英文中 square 也有平方的意思），你为什么不试着把你的卡特兰数平方（square）一下呢！”。这引来了一片欢呼，而你开始思考如何将卡特兰序列平方……

任务

设 $C_n$ 为上文定义的第 $n$ 个卡特兰数。通过考虑卡特兰数序列 $(C_n)_{n\ge 0}$，我们可以通过计算 $(C_n)_{n\ge 0}$ 与自身的柯西乘积（或离散卷积）来定义一个序列 $(S_n)_{n\ge 0}$，这对应于“将卡特兰序列平方”，即：

$$S_n = \sum_{k=0}^{n} C_k C_{n-k}$$

你的任务是编写一个程序来计算数值 $S_n$。

输入格式

输入包含一行，包含一个非负整数 $n$，其中 $0 \le n \le 5\,000$。

输出格式

输出一行，包含 $S_n$。

样例

输入样例 1

0

输出样例 1

1

输入样例 2

59

输出样例 2

1583850964596120042686772779038896

说明

要理解为什么说 $(S_n)_{n\ge 0}$ 对应于卡特兰序列的平方，我们可以看一下幂级数的柯西乘积。假设 $p(x) = \sum_{n=0}^{\infty} a_n x^n$ 且 $q(x) = \sum_{n=0}^{\infty} b_n x^n$，那么 $p(x) \cdot q(x) = \sum_{n=0}^{\infty} c_n x^n$，其中 $c_n = \sum_{k=0}^{n} a_k b_{n-k}$。