Description

由于天依刚睡醒，害怕第一题的题面就迷糊了大家，所以本题只有简要题意。（其实是实在编不下去了。）

设 $\sigma$ 为任意一个长度为 $n$ 的排列，$\tau(\sigma)$ 表示其中的逆序对个数，请求出

$$\sum_\sigma 2^{\tau(\sigma)}$$

对 $(10^9+7)$ 取模的结果。

Input Format

输入一行一个整数 $n$，表示排列的长度。

Output Format

输出一行一个整数，表示所求得的答案。

3

21

Hint

题意解释

本节为部分选手介绍逆序对的定义，对此熟悉的选手可以跳过本节。

对于长度为 $n$ 的排列 $\sigma$，假设下标从 $1$ 开始，那么我们称 $(i,j)$ 构成逆序对，当且仅当 $1\le i<j\le n$，并且 $\sigma_i>\sigma_j$；$\tau(\sigma)$ 则表示总共有多少对不同的 $(i,j)$ 满足上述条件。

举个例子，对于排列 $\sigma=\lang 2,4,1,3\rang$，有逆序对 $(1,3),(2,3),(2,4)$，所以 $\tau(\sigma)=3$。可见只要 $\sigma$ 中元素的大小关系确定，$\tau(\sigma)$ 就是确定的。

样例 #1 解释

$$\begin{aligned} \sum_{\sigma}2^{\tau(\sigma)} &= 2^{\tau(\lang 1,2,3\rang)}+2^{\tau(\lang 1,3,2\rang)}+2^{\tau(\lang 2,1,3\rang)}+2^{\tau(\lang 2,3,1\rang)}+2^{\tau(\lang 3,1,2\rang)}+2^{\tau(\lang 3,2,1\rang)}\\ &= 2^0+2^1+2^1+2^2+2^2+2^3\\ &= 21. \end{aligned}$$

数据规模与约定

本题采用 Subtask 的计分方式。

子任务编号	$n$	分值
$1$	$\le4$	$5$
$2$	$\le10$	$20$
$3$	$\le100$
$4$	$\le10^3$	$25$
$5$	$\le10^7$	$30$