#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Factorial - Classic Problems | Repovive

CLS7. Factorial

1s256 MB

The factorial of $n$ is defined as:

$0! = 1$
$n! = n \times (n-1)!$ for $n \ge 1$

Given $n$ , compute $n! \mod (10^9 + 7)$ .

Constraints

$0 \le n \le 10^6$

Input

$n$

Output

$n! \mod (10^9 + 7)$

Samples

Input

Explanation

For this input, the required output is 1.

Output

Input

Explanation

For this input, the required output is 120.

Output

Input

Explanation

For this input, the required output is 3628800.

Output

Input

Explanation

For this input, the required output is 641419708.

Output

641419708

The factorial of $n$ is defined as:

$0! = 1$
$n! = n \times (n-1)!$ for $n \ge 1$

Given $n$ , compute $n! \mod (10^9 + 7)$ .

$0 \le n \le 10^6$

$n! \mod (10^9 + 7)$