题目描述

有一个集合 $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$ 取模。

2

4

1000

476463243

1919810

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}{你：我*****}$$