X 轴上有 2n 个点 ，相邻点之间的间距都为1，虎哥正在考虑了将这 2n 个点分成 n 对的方法。
配对定义如下： 
每个点都只用一次。对于每 2 个不同的段 A 和 B，则至少满足以下一项： 
1. 段 A 和 B 中的一个完全位于另一个内部。 
2. A 和 B 的长度相同。

图中（A）、（B）可行，（C）不可行。

虎哥现在想知道，这2n个点有多少种连接方法，你能帮他吗？

样例2输入

100

样例2输出

688750769

样例3输入

2

样例3输出

3

样例4输入

1

样例4输出

1

上图中，左边对应的是样例1，右图对应的是样例3.

天梯赛#4E