Mindiff and Maxdiff
题号：NC17491
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

Given a set X of distinct positive integers, denote mindiff(X) as the minimum absolute difference of two distinct elements in X and maxdiff(X) as the maximum absolute difference of two distinct elements in X. If the size of X is strictly less than 2, define mindiff(X) and maxdiff(X) as 0.

Find the sum of mindiffmaxdiff(T), where T varies over all possible subsets of S = {1, 2, ..., n}, modulo 109 + 7.

输入描述:

The input contains a single integer, n (1 ≤ n ≤ 5 * 105).

输出描述:

Output a single integer, the answer to the problem.
示例1

输入

复制 
3

输出

复制 
8

说明

For sample 1, the subsets with size ≤ 1 will not contribute to the answer.

mindiff(\{1, 2\}) \cdotmaxdiff(\{1, 2\}) = 1 \cdot 1 = 1

mindiff(\{2, 3\}) \cdotmaxdiff(\{2, 3\}) = 1 \cdot 1 = 1

mindiff(\{1, 3\}) \cdotmaxdiff(\{1, 3\}) = 2 \cdot 2 = 4

mindiff(\{1, 2, 3\}) \cdotmaxdiff(\{1, 2, 3\}) = 1 \cdot 2 = 2

The total sum is 8.
示例2

输入

复制 
5

输出

复制 
106