Average Inversions in Permutations

In this problem, we consider permutations of n elements. A permutation of n elements is a sequence of n distinct natural numbers from 1 to n. Given two permutations \(a_1,a_2,\ldots,a_n\) and \(b_1,b_2,\ldots,b_n\), their composition is defined as the permutation \(a_{b_1},a_{b_2},\ldots,a_{b_n}\).

An inversion in a permutation \(p_1,p_2,\ldots,p_n\) is any pair \((i,j)\) such that \(ip_j\). It is a well-known fact that the average number of inversions in any permutation of n elements is given by:

\(\frac{n(n-1)}{4}\)

Bytie is a big fan of permutations. He has a collection of his favorite permutations and he composes them (in any order, possibly using some multiple times) to generate all possible permutations without any repeats. Once he has written down every possible permutation, he wonders: what is the average number of inversions in the generated list? Your task is to compute this average value modulo \(10^9+7\).

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10⁹), representing the number of elements in the permutation.

Note: Although the upper bound for n is large, the answer can be computed using the formula for the average number of inversions.

outputFormat

Output a single integer, the value of \(\frac{n(n-1)}{4}\) modulo \(10^9+7\).

sample

1

0