#4667. 模板. 阶乘 mod 大质数

模板. 阶乘 mod 大质数

Description

这是一道模板题。

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

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

Input

TT 组数据。

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

Output

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

Samples

1
5
120

Limitation

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