### 问题描述 小蓝有一个集合 $A=\left \{ 1,2,3\dots, n\right \}$。 凯莉很羡慕小蓝的集合，于是她也创造了一个集合 $B$，并且将集合 $B$ 中的元素按照从大到小的顺序进行排序，即 $B= \left \{ b_1,b_2,\dots,b_{cnt}\right \}$（$cnt$ 为集合元素个数）。 凯莉觉得还有点不满足，于是又创造了一个函数 $G(B)$，定义 $G(B)=\sum_{i=1}^{cnt } ((-1)^{i+1 }\times b_i)$。 例如，$G(\left \{ 1,2,4,6,9\right \})=9-6+4-2+1=6$。 特别地，$G(\emptyset)=0$。 现在，给定集合 $A=\left \{ 1,2,3\dots, n\right \}$，凯莉想知道对于 $A$ 的任意子集 $P$，求出 $G(P)$ 的总和。 因为答案可能较大，所以输出对 $911451407$ 取模后的结果。 ### 输入格式 输入包含一个整数 $n$，含义见上文。 ### 输出格式 输出一个整数，表示模 $911451407$ 意义下的答案。 ### 样例输入 ``` 2 ``` ### 样例输出 ``` 4 ``` ### 评测数据规模 对于所有评测数据，$1\leq{n}\leq{10^{16 }}$。