[KMOI R1] 集合 First
题目描述
有一个集合 $A=\{1,2,3\dots,n\}$。
定义交替和 $G(B)$ 如下：
- 把集合 $B$ 中的元素从大到小排序，得到 $B=\{b_1,b_2\dots,b_{cnt}\}$（$cnt$ 为集合元素个数）。则 $G(B)=\sum\limits_{i=1}^{cnt}\Big((-1)^{i+1}\times b_i\Big)$。
例如 $G(\{1,2,4,6,9\})=9-6+4-2+1=6$。
特别地，$G(\empty)=0$。
现在，给定集合 $A=\{1,2,3,\dots,n\}$，小谢想知道对于 $A$ 的**任意子集 $P$**，求出 $G(P)$ 的总和。
由于小谢太菜了，所以请你帮帮忙，**答案对 $911451407$ 取模。**
输入输出格式
输入格式
一个正整数 $n$，表示给定的集合 $A=\{1,2,3,\dots,n\}$。
输出格式
一个正整数 $ans$，表示对于 $A$ 的**任意子集 $P$**，$G(P)$ 的总和。
**答案对 $911451407$ 取模。**
输入输出样例
输入样例 #1
2输出样例 #1
4输入样例 #2
1000输出样例 #2
476463243输入样例 #3
1919810输出样例 #3
193840227说明
## 样例 $1$ 解释
$G(\empty)=0$
$G(\{1\})=1$
$G(\{1,2\})=1$
$G(\{2\})=2$
故 $ans=G(\empty)+G(\{1\})+G(\{1,2\})+G(\{2\})=4$。
## 数据范围
**本题采用 subtask 捆绑测试。**
|子任务编号| 测试点 | $n\le$ | 分值 |
|:-:| :----------: | :----------: | :----------: |
|$1$| $1,2$ | $20$ | $15$ |
|$2$| $3\sim5$ | $10^3$ | $10$ |
|$3$| $6\sim10$ | $10^{9}$ | $30$ |
|$4$| $11\sim17$ | $10^{16}$ | $45$ |
对于 $100\%$ 的数据：$1\le n\le 10^{16}$。
## 后记
$$\color{orange}{小谢：别打我，我下次再也不研究大小超过\ 30\ 的集合了。}$$
$$\color{purple}{你：我*****}$$