Description

Since Tianyi has just woken up and is afraid the statement of the first problem will make everyone confused, this problem only provides a brief description. (Actually, I really cannot make up more story.)

Let $\sigma$ be any permutation of length $n$, and let $\tau(\sigma)$ denote the number of inversion pairs in it. Compute

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

modulo $(10^9+7)$.

Input Format

Input one integer $n$ in a single line, denoting the length of the permutation.

Output Format

Output one integer in a single line, denoting the required answer.

3

21

Hint

Explanation of the statement

This section introduces the definition of inversion pairs for some contestants. If you are familiar with it, you may skip this section.

For a permutation $\sigma$ of length $n$, assuming indices start from $1$, we say $(i,j)$ forms an inversion pair if and only if $1\le i<j\le n$ and $\sigma_i>\sigma_j$. $\tau(\sigma)$ denotes how many different pairs $(i,j)$ satisfy the condition above.

For example, for the permutation $\sigma=\lang 2,4,1,3\rang$, the inversion pairs are $(1,3),(2,3),(2,4)$, so $\tau(\sigma)=3$. It can be seen that as long as the relative order of the elements in $\sigma$ is fixed, $\tau(\sigma)$ is fixed.

Sample #1 Explanation

$$\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}$$

Constraints and Notes

This problem uses Subtask-based scoring.

Subtask ID	$n$	Score
$1$	$\le4$	$5$
$2$	$\le10$	$20$
$3$	$\le100$
$4$	$\le10^3$	$25$
$5$	$\le10^7$	$30$

Translated by ChatGPT 5