← 返回题目列表

Codeforces · 1152/D

D. Neko 和 Aki 的恶作剧

中文机器翻译题面 查看原题

Neko 正在 Aki 家的后院玩他的玩具。阿吉决定跟他搞个恶作剧,偷偷把猫薄荷放进了 Neko 的玩具里。不幸的是,他太过分了,把一整袋猫薄荷放进了玩具里……

Neko花了一整天的时间才恢复正常。 Neko 向 Aki 报告说他看到了很多奇怪的东西,包括长度为 $$$2n$$$ 的所有正确括号序列的字典树。

正确的括号序列定义如下:

- 空序列是正确的括号序列,
- 如果 $$$s$$$ 是正确的括号序列,则 $$$(\,s\,)$$$ 是正确的括号序列,
- 如果 $$$s$$$ 和 $$$t$$$ 是正确的括号序列,则 $$$st$$$ 也是正确的括号序列。

例如,字符串“(())”、“()()”形成正确的括号序列,而“)(”和“((”则不然。

Aki 然后提出了一个有趣的问题:这个 trie 中最大匹配(最大的边集,使得不存在具有公共顶点的两条边)的大小是多少?由于答案可能相当大,因此打印它对 $$$10^9 + 7$$$ 取模。

输入

唯一一行包含单个整数 $$$n$$$ ($$$1 \le n \le 1000$$$)。

输出

精确打印一个整数——特里树中最大匹配的大小。由于答案可能相当大,因此打印它对 $$$10^9 + 7$$$ 取模。

示例

输入 #1

1

输出 #1

1

输入 #2

2

输出 #2

3

输入 #3

3

输出 #3

9

注意

下图展示了前两个示例中的尝试(为了清楚起见,圆括号替换为尖括号)。最大匹配以蓝色突出显示。