Alternating Subset Sum

You are given a set \(A = \{1, 2, 3, \dots, n\}\). For any subset \(P\) of \(A\), define its alternating sum \(G(P)\) as follows:

If \(P\) is empty, then \(G(P) = 0\). Otherwise, sort the elements of \(P\) in descending order to obtain \(P = \{b_1, b_2, \dots, b_{cnt}\}\, (cnt\text{ is the number of elements in }P). Then, define

[ G(P) = \sum_{i=1}^{cnt} (-1)^{i+1} \times b_i. ]

For example, for \(P=\{1,2,4,6,9\}\), we have

[ G({1,2,4,6,9}) = 9 - 6 + 4 - 2 + 1 = 6. ]

Your task is to compute the sum of \(G(P)\) over all subsets \(P\) of \(A\). Since the answer can be very large, output it modulo \(911451407\).

Hint: It can be shown that the answer simplifies to \(n \times 2^{n-1}\) (modulo \(911451407\)).

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^9\)).

outputFormat

Output a single integer, the sum of \(G(P)\) over all subsets \(P\) of \(A\), taken modulo \(911451407\).

sample

1

1