排序
题号：NC18392
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小O有一个长度为2n的1到2n的排列。他现在想干这样一件事情：首先他把这个排列随机地打乱顺序。然后他把奇数位置的数从小到大重新排序。接着他统计最后这个排列的逆序对个数。现在小O想知道，期望的逆序对数是多少？答案对109+7取模。
一个例子是这样的，小O有一个长度为6的排列，他一开始打乱顺序后排列变成4,6,1,5,3,2，排序后变成1,6,3,5,4,2。逆序对数为8。

输入描述:

第一行一个整数n。
数据保证n ≤ 50000000

输出描述:

一行一个整数代表期望的逆序对数。
示例1

输入

复制 
2

输出

复制 
166666670