题目描述

这是一道模板题。

询问 $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$。