Description

食欲旺盛だが運動不足気味のカトーくんは、ダイエットのため、油そばを $N$ グラム食べたらスクワットを $N!$ 回することに決めた。しかし、頭のいいカトーくんは、$N!$ は爆発的な回数になってしまい、スクワットをこなせないことに気づいた。

そこで、今年は2017年であることにあやかり、$N!$ を $2017$ で割った余りの回数だけスクワットを行うことに変更した。

与えらえる $N$ に対して、カトーくんがスクワットをする回数を求めよ。

なお、整数 $a,b$ と $p$ に対して、 $(a \times b)\bmod{p} = ( (a \bmod{p}) \times b) \bmod{p}$ が成り立つ。

Constraints

1つの入力ファイルは複数のテストケースからなる。

入力ファイルの最初の1行目にはテストケースの個数 $T$ が記される $(1 \leq T \leq 1000)$。

2行目以降には、$T$ 個のテストケースが記述されており、各テストケースは次の形式で表される。

$N$

各テストケースに対して、カトーくんがスクワットをする回数 $(N! \bmod 2017)$ を1行ずつ出力せよ。

2
4
29

24
367

$29! \bmod{2017} = 8841761993739701954543616000000 \bmod{2017} = 367$ です。剰余を取ることで、スクワットの回数を現実的なものに抑えることができました。オーバーフローに気を付けてください。

また、largeに取り組むときは計算時間を少し考えてみましょう。工夫できる箇所はありませんか...?