P9708 [KMOI R1] Set First

There is a set $A=\{1,2,3\dots,n\}$. Define the alternating sum $G(B)$ as follows: - Sort the elements in set $B$ from large to small, obtaining $B=\{b_1,b_2\dots,b_{cnt}\}$ ($cnt$ is the number of elements in the set). Then $G(B)=\sum\limits_{i=1}^{cnt}\Big((-1)^{i+1}\times b_i\Big)$. For example, $G(\{1,2,4,6,9\})=9-6+4-2+1=6$. In particular, $G(\empty)=0$. Now, given the set $A=\{1,2,3,\dots,n\}$, Xiaoxie wants to know: for **any subset $P$ of $A$**, compute the total sum of $G(P)$. Because Xiaoxie is too weak, please help. **Take the answer modulo $911451407$.**

A positive integer $n$, representing the given set $A=\{1,2,3,\dots,n\}$.

A positive integer $ans$, representing the total sum of $G(P)$ over **any subset $P$ of $A$**. **The answer is taken modulo $911451407$.**

## Explanation for Sample $1$ $G(\empty)=0$. $G(\{1\})=1$. $G(\{1,2\})=1$. $G(\{2\})=2$. Therefore, $ans=G(\empty)+G(\{1\})+G(\{1,2\})+G(\{2\})=4$. ## Constraints **This problem uses bundled subtask testdata.** | Subtask ID | Test Points | $n\le$ | Score | |:-:| :----------: | :----------: | :----------: | | $1$ | $1,2$ | $20$ | $15$ | | $2$ | $3\sim5$ | $10^3$ | $10$ | | $3$ | $6\sim10$ | $10^{9}$ | $30$ | | $4$ | $11\sim17$ | $10^{16}$ | $45$ | For $100\%$ of the testdata: $1\le n\le 10^{16}$. ## Postscript $$\color{orange}{Xiaoxie: Don't hit me, I will never study sets with size greater than\ 30\ again next time.}$$ $$\color{purple}{You: I*****}$$ Translated by ChatGPT 5