题目描述

你的任务是计算将数字 $1, 2, \ldots, n$ 分成两组，使得这两组的元素和相等的分法总数。

例如，当 $n = 7$ 时，存在四种解决方案：

• $\{1, 3, 4, 6\}$ 和 $\{2, 5, 7\}$
• $\{1, 2, 5, 6\}$ 和 $\{3, 4, 7\}$
• $\{1, 2, 4, 7\}$ 和 $\{3, 5, 6\}$
• $\{1, 6, 7\}$ 和 $\{2, 3, 4, 5\}$

要求输出总的分法数，结果对 $10^9 + 7$ 取模。

输入格式

唯一的输入行包含一个整数 $n$。

输出格式

输出一个整数，表示将数字 $1, 2, \ldots, n$ 分成两组，且两组和相等的分法数，对 $10^9 + 7$ 取模。

样例

7

4

数据范围

• $1 \le n \le 500$