VZLA2019B - Being a centipede is tough

Ciempierre is a funny n-pede, and arthropod with exactly N legs. He likes clothing, and today he bought N different shoes and N different socks. To get dressed, he has to put exactly one sock and one shoe on every leg.

He is a bit eccentric, and he wants to get dressed every morning in a different way. He defines a way of getting dressed as the order he puts his clothes on. In one step, he can choose one leg and one sock or one shoe. Two ways of getting dressed are different if there is at least one step where he chooses a different leg or, in case of using the same leg, a different sock or shoe.

For example, if Ciempierre has two legs he will buy two different socks and two different shoes. One way of getting dressed is:

  1. Put sock 1 on leg 1
  2. Put sock 2 on leg 2
  3. Put shoe 1 on leg 1
  4. Put shoe 2 on leg 2

Notice that two ways are not necessarily equal if they make Ciempierre look the same. For example, if we swap the first and second steps on the example explained above, it would have been a different way of getting dressed, but his look would had been the same.

Not all the ways of getting dressed are valid, though. Ciempierre can't put a shoe on a leg before putting a sock on that leg first.

Given the number of legs Ciempierre has, can you calculate the number of different ways he can get dressed?

Input

The first and only line of the input will have an integer N, being the number of legs Ciempierre has, and for instance the number of different socks and different shoes he bought.

Output

Print the number of different ways he can get dressed. As this number can be really big, you must print it modulo 10^9 + 7

Example

Input:
2

Output:
24
Input:
3

Output:
3240
Input:
1

Output:
1
Input:
10

Output:
540458589

Constraints

1 ≤ N ≤ 10^5


Added by:Samuel Nacache
Date:2019-10-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Rubmary Rojas - Used for Venezuelan 2019 ICPC Local Contest

hide comments
2019-12-07 04:37:38
And here comes half of Indonesia with the same solution... :/
2019-10-28 22:56:31
Might be easier for someone doing combinatorics daily, but I had to put in a lot of work to arrive at the solution. Nice one.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.