[AdditionalFile170.zip](file://AdditionalFile170.zip?type=additional_file)

#170. 阶乘 mod 大质数

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB 通过: 134 | 提交: 323

题目描述

这是一道模板题。

询问 $n!$ 对 $1000391835649$ 取模的结果。

$1000391835649 = 2^{26} \times 3 \times 4969 + 1$，是一个 $10^{12}$ 级别的大质数，最小原根为 $7$。

输入格式

$T$ 组数据。

每组数据一个正整数表示 $n$。

输出格式

$T$ 行，一行一个整数表示答案。

样例

输入

1
5

输出

120

数据范围与提示

100% 的数据保证 $1 \le T \le 50, 1 \le n < 1000391835649$。