Problem Description

There is a set \( A = \{1, 2, 3, \dots, n\} \).

Define the alternating sum \( G(B) \) as follows:

• Sort the elements of set \( B \) in descending order, resulting in \( B = \{b_1, b_2, \dots, b_{cnt}\} \) (where \( cnt \) is the number of elements in the set). Then \( G(B) = \sum_{i=1}^{cnt} \left( (-1)^{i+1} \times b_i \right) \).

For example, \( G(\{1, 2, 4, 6, 9\}) = 9 - 6 + 4 - 2 + 1 = 6 \).

Specifically, \( G(\emptyset) = 0 \).

Given the set \( A = \{1, 2, 3, \dots, n\} \), Xie wants to know the sum of \( G(P) \) for any subset \( P \) of \( A \).

Since Xie is too inexperienced, please help him, and the answer should be taken modulo \( 911451407 \).

Input Format

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

Output Format

A single positive integer \( ans \), representing the sum of \( G(P) \) for any subset \( P \) of \( A \).

The answer should be taken modulo \( 911451407 \).

Sample Input and Output

Sample Input #1

2

Sample Output #1

4

Sample Input #2

1000

Sample Output #2

476463243

Sample Input #3

1919810

Sample Output #3

193840227

Notes

Sample #1 Explanation

\( G(\emptyset) = 0 \)

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

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

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

Thus, \( ans = G(\emptyset) + G(\{1\}) + G(\{1, 2\}) + G(\{2\}) = 4 \).

Data Range

This problem uses subtask bundling for testing.

For \( 100\% \) of the data: \( 1 \le n \le 10^{16} \).

见题面 Input 部分

见题面 Output 部分