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 neccesarily 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