Permutation Inversion Sum

Given a positive integer (n), consider all permutations (\sigma) of the set ({1,2,\ldots,n}). Let (\tau(\sigma)) denote the number of inversion pairs in (\sigma). You are required to compute

[ \sum_{\sigma} 2^{\tau(\sigma)} \mod (10^9+7), ]

which, using a known combinatorial identity, can be shown to equal

[ \prod_{i=1}^{n} (2^i-1) \mod (10^9+7). ]

Note: The formula arises from the generating function for inversions in permutations.

inputFormat

The input consists of a single integer (n) on one line.

outputFormat

Output the value of

[ \prod_{i=1}^{n} (2^i-1) \mod (10^9+7), ]

as a single integer.

sample

1

1