Background

  "From this day on, the snow melts and the wind turns gentle; even plum blossoms should yield to the new willow twigs."

---

  "We have to go back to school tomorrow."

  Gray long hair was slowly combed through by the person behind her, again and again. She woke up on the last lazy morning of the holiday, sleepily whispering with the first ray of spring sunlight. Her gaze followed the birds outside the window, then stopped on that cluster of brown, bare branches.

  "Tianyi?"

  The crimson eyes looked over as well. For a moment, silence.

  "If I could tell it that today is the Start of Spring, that it is spring..."

  "Then it would sprout and flourish, and become something wonderful outside our window, either red or green."

  "—Because it should be like that. Let it be so, I hope."

---

  Start of Spring  "A fledgling stands on a cliff / spreads its wings / dreams on the horizon / lit by a beam of light."

Problem 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