首页 > 试题广场 >

Mindiff and Maxdiff

[编程题]Mindiff and Maxdiff
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
算法知识视频讲解
开通博客

暂无题解

问题信息

组合数学
难度：
0条回答 6浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Mindiff and Maxdiff

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号