#P9708. [KMOI R1] 集合 First

[KMOI R1] 集合 First

题目描述

有一个集合 A={1,2,3,n}A=\{1,2,3\dots,n\}

定义交替和 G(B)G(B) 如下:

  • 把集合 BB 中的元素从大到小排序,得到 B={b1,b2,bcnt}B=\{b_1,b_2\dots,b_{cnt}\}cntcnt 为集合元素个数)。则 $G(B)=\sum\limits_{i=1}^{cnt}\Big((-1)^{i+1}\times b_i\Big)$。

例如 G({1,2,4,6,9})=96+42+1=6G(\{1,2,4,6,9\})=9-6+4-2+1=6

特别地,G()=0G(\empty)=0

现在,给定集合 A={1,2,3,,n}A=\{1,2,3,\dots,n\},小谢想知道对于 AA任意子集 PP,求出 G(P)G(P) 的总和。

由于小谢太菜了,所以请你帮帮忙,答案对 911451407911451407 取模。

输入格式

一个正整数 nn,表示给定的集合 A={1,2,3,,n}A=\{1,2,3,\dots,n\}

输出格式

一个正整数 ansans,表示对于 AA任意子集 PPG(P)G(P) 的总和。

答案对 911451407911451407 取模。

2
4
1000
476463243
1919810
193840227

提示

样例 11 解释

G()=0G(\empty)=0

G({1})=1G(\{1\})=1

G({1,2})=1G(\{1,2\})=1

G({2})=2G(\{2\})=2

ans=G()+G({1})+G({1,2})+G({2})=4ans=G(\empty)+G(\{1\})+G(\{1,2\})+G(\{2\})=4

数据范围

本题采用 subtask 捆绑测试。

子任务编号 测试点 nn\le 分值
11 1,21,2 2020 1515
22 353\sim5 10310^3 1010
33 6106\sim10 10910^{9} 3030
44 111711\sim17 101610^{16} 4545

对于 100%100\% 的数据:1n10161\le n\le 10^{16}

后记

小谢:别打我,我下次再也不研究大小超过 30 的集合了。\color{orange}{小谢:别打我,我下次再也不研究大小超过\ 30\ 的集合了。} 你:我\color{purple}{你:我*****}