题目描述

伊藤诚手中有一个函数 $f(n)=n!\ (n\ge 0)$，他想快速计算它。

幸运地，他最近看到两篇论文 光速阶乘算法、龟速阶乘算法，他通过阅读文章，迅速实现了论文中的实现。

他迫不及待地向你展示了他的学习成果。

你很不服气，请你仔细阅读两篇论文中的内容，并尝试实现它们的做法。

输入格式

本题有多组测试数据。

第一行一个正整数 $t$ 为数据组数。

对于每组数据，一行一个正整数 $n$。

输出格式

对于每组数据，一行一个正整数，为 $f(n)$ 的答案。答案对 $20091119$ 取模。

样例

3
0
2
4

1
2
24

数据范围

对于 $40\%$ 的数据，$1\le t\le 5,0\le n\le 10$。

对于 $100\%$ 的数据，$1\le t\le 5,0\le n \le 10^{100}$。