题目描述

给出一个数字 $n$ ，求 $n!$ 除以 $10^9 + 7$ 的余数。

输入格式

第一行输入一个正整数 $n$。

输出格式

输出一个非负整数，表示答案。

3

6

提示

数据保证均匀分布，$1 \le n \le 10^9$。

第 $i$ 个测试点的 $n$ 为 $(i - 1) \% 9 \times 10^{ \lfloor \frac{(i - 1)}{9} \rfloor}$。