#2108. 阶乘 mod 大质数

阶乘 mod 大质数

题目描述

这是一道模板题。

询问 n!n!10003918356491000391835649 取模的结果。

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

输入格式

TT 组数据。

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

输出格式

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

样例

1
5
120

数据范围与提示

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