CSES1093 两个集合 II
#CS1093. 两个集合 II
两个集合 II
题目背景
翻译自 CSES-1093 题。
题目描述
你的任务是计算将数字 1,2,…,n1,2,…,n1,2,…,n 分成两组，使得这两组的元素和相等的分法总数。
例如，当 n=7 时，存在四种解决方案：
-
1,3,4,6{1,3,4,6}1,3,4,6 和 2,5,7{2,5,7}2,5,7
-
1,2,5,6{1,2,5,6}1,2,5,6 和 3,4,7{3,4,7}3,4,7
-
1,2,4,7{1,2,4,7}1,2,4,7 和 3,5,6{3,5,6}3,5,6
-
1,6,7{1,6,7}1,6,7 和 2,3,4,5{2,3,4,5}2,3,4,5
要求输出总的分法数，结果对 109+710^9+7109+7 取模。
输入格式
唯一的输入行包含一个整数 n。
输出格式
输出一个整数，表示将数字 1,2,…,n1,2,…,n1,2,…,n 分成两组，且两组和相等的分法数，对 109+710^9+7109+7 取模。
样例
7
4
说明/提示