Description

这是一道模板题。

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

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

Input

$T$ 组数据。

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

Output

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

Samples

1
5

120

Limitation

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