CF1152D Neko and Aki's Prank

Neko 正在 Aki 家的后院玩他的玩具。Aki 决定恶作剧一下，偷偷地在 Neko 的玩具里放了猫薄荷。不幸的是，他下手太重，把整袋猫薄荷都倒进了玩具里…… Neko 花了一整天才恢复正常。他向 Aki 报告说，他看到了很多奇怪的东西，包括一个包含所有长度为 $2n$ 的合法括号序列的 [trie](https://en.wikipedia.org/wiki/Trie)。 合法括号序列的定义如下： - 空序列是合法括号序列； - 如果 $s$ 是合法括号序列，那么 $(\,s\,)$ 也是合法括号序列； - 如果 $s$ 和 $t$ 都是合法括号序列，那么 $st$ 也是合法括号序列。 例如，字符串 "(())"、"()()" 是合法括号序列，而 ")(" 和 "((" 不是。 Aki 随后想出了一个有趣的问题：这个 trie 的最大匹配（即没有两个边有公共顶点的最大边集）的大小是多少？由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

输入仅一行，包含一个整数 $n$（$1 \le n \le 1000$）。

输出一个整数，表示该 trie 的最大匹配的大小。由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

下图展示了前两个样例的 trie（为清晰起见，圆括号被替换为尖括号）。最大匹配用蓝色高亮显示。   由 ChatGPT 4.1 翻译