You need to find the product of first n factorials 1! * 2! * ... * n! modulo 109546051211.

Input

One integer n (1 <= n <= 10000000)

Output

The answer.

Example

Input:
5

Output:
34560