Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Perplexity of Permutations

By TarifEzaz · Limits 1s, 512 MB

A permutation of N integers from 1 to N is an array where each number has appeared exactly once in the array. The array [1,3,2,5,4] is a permutation of 5 numbers. For any array of size N, there are N factorial permutations in total.

We define perplexity as the sum of absolute difference between the adjacent elements of an array. For example, the array [1,3,2] has the total perplexity of 3.

In this problem, you will be given N, you will have to answer the sum of perplexity of all the permutations of 1 to N.

Input

The only line of input contains an integer N (≤105), the size of the array.

Output

Output one number, the total sum of perplexities across all the permutations of 1 to N. Since the result can be very large, print the remainder of the result, when divided with 100007.

Sample

InputOutput
2
2

Discussion

Statistics


40% Solution Ratio

fsshakkhorEarliest, 3M ago

fire_tornadoFastest, 0.0s

fsshakkhorLightest, 131 kB

fire_tornadoShortest, 1311B

Submit

Login to submit