题目背景

翻译自 CSES-1093 题。

题目描述

你的任务是计算将数字 $1,2,…,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,…,n$ 分成两组，且两组和相等的分法数，对 $10^9+7$ 取模。

样例

7

4

说明/提示

$1 \leq n \leq 500$。