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
注意
下图展示了前两个示例中的尝试(为了清楚起见,圆括号替换为尖括号)。最大匹配以蓝色突出显示。