#170. 阶乘 mod 大质数

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zhouyuyang

题目描述

这是一道模板题。

询问 n! 1000391835649 取模的结果。

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

输入格式

T 组数据。

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

输出格式

T 行,一行一个整数表示答案。

样例

输入

1
5

输出

120

数据范围与提示

100\% 的数据保证 1 \leq T \leq 50,1 \leq n < 1000391835649