{"raw_statement":[{"iden":"statement","content":"有一个集合 $A=\\{1,2,3\\dots,n\\}$。\n\n定义交替和 $G(B)$ 如下：\n\n- 把集合 $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)$。\n\n例如 $G(\\{1,2,4,6,9\\})=9-6+4-2+1=6$。\n\n特别地，$G(\\empty)=0$。\n\n现在，给定集合 $A=\\{1,2,3,\\dots,n\\}$，小谢想知道对于 $A$ 的**任意子集 $P$**，求出 $G(P)$ 的总和。\n\n由于小谢太菜了，所以请你帮帮忙，**答案对 $911451407$ 取模。**"},{"iden":"input","content":"一个正整数 $n$，表示给定的集合 $A=\\{1,2,3,\\dots,n\\}$。"},{"iden":"output","content":"一个正整数 $ans$，表示对于 $A$ 的**任意子集 $P$**，$G(P)$ 的总和。\n\n**答案对 $911451407$ 取模。**"},{"iden":"note","content":"## 样例 $1$ 解释\n$G(\\empty)=0$\n\n$G(\\{1\\})=1$\n\n$G(\\{1,2\\})=1$\n\n$G(\\{2\\})=2$\n\n故 $ans=G(\\empty)+G(\\{1\\})+G(\\{1,2\\})+G(\\{2\\})=4$。\n\n## 数据范围\n\n**本题采用 subtask 捆绑测试。**\n\n|子任务编号| 测试点 | $n\\le$ | 分值 |\n|:-:| :----------: | :----------: | :----------: |\n|$1$| $1,2$ | $20$ | $15$ |\n|$2$| $3\\sim5$ | $10^3$ | $10$ |\n|$3$| $6\\sim10$ | $10^{9}$ | $30$ |\n|$4$| $11\\sim17$ | $10^{16}$ | $45$ |\n\n对于 $100\\%$ 的数据：$1\\le n\\le 10^{16}$。\n\n## 后记\n\n$$\\color{orange}{小谢：别打我，我下次再也不研究大小超过\\ 30\\ 的集合了。}$$\n\n$$\\color{purple}{你：我*****}$$"}],"translated_statement":null,"sample_group":[["2","4"],["1000","476463243"],["1919810","193840227"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}