Description

据说今天是男神$SL$的生日，但是他很低调，轻轻地送了一道大水题...

就是传说中的 $" N !"$

Format

Input

每一行包含一个整数$N(0 \leq N\leq10^9)$.

Output

对于每个数，输出 $N!$ $mod$ $2009$

Samples

4
5

24
120