Problem Description

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$.

Input Format

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

Output Format

A positive integer $ans$, representing the total sum of $G(P)$ over any subset $P$ of $A$.

The answer is taken modulo $911451407$.

2

4

1000

476463243

1919810

193840227

Hint

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