由于天依刚睡醒，害怕第一题的题面就迷糊了大家，所以本题只有简要题意。~~（其实是实在编不下去了。）~~
设 $\sigma$ 为任意一个长度为 $n$ 的排列，$\tau(\sigma)$ 表示其中的逆序对个数，请求出
$$
\sum_\sigma 2^{\tau(\sigma)}
$$
对 $(10^9+7)$ 取模的结果。
## Input
输入一行一个整数 $n$，表示排列的长度。
## Output
输出一行一个整数，表示所求得的答案。
[samples]
## Background
  「从此雪消风自软，梅花合让柳条新」
---
  “明天就要返校了呢。”
  灰色的长发被身后的人儿慢慢地顺着，顺着，于假期最后一个慵懒的清晨醒来，与春日的第一抹阳光迷迷糊糊地耳语，她的目光随着点过窗外的鸟雀，停留在那丛褐色的光秃枝丫。
  “天依？”
  赤红色的眸子随之望去，片刻，静默。
  “如果我能告诉它，今天是立春，是春天的……”
  “那么它会抽芽，繁盛，会成为我们窗外或红或绿的美妙。”
  “——因为它本该如此，希望如此吧。”
---
  **立春** 「雏鸟站在悬崖上 展开了翅膀 地平线上的梦想 照进一缕光」
## Note
#### 题意解释
本节为部分选手介绍**逆序对的定义**，对此熟悉的选手可以跳过本节。
对于长度为 $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$ | $20$ |
| $4$ | $\le10^3$ | $25$ |
| $5$ | $\le10^7$ | $30$ |