题目描述

组合数 $\binom{n}{m}$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1,2,3)$ 三个物品中选择两个物品可以有 $(1,2),(1,3),(2,3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $\binom{n}{m}$ 的一般公式：

其中 $n!=1\times2\times\cdots\times n$；特别地，定义 $0!=1$。

看到这里，你可能会想到，某年NOIP不是也有道组合数问题吗，题目描述甚至还很像！？

可惜两道题有亿点点区别。

我们利用组合数定义一下$f(n,k)$，他等于：

特别地，规定 $f(n,0)=1$。

然后麻烦你求解：

输入格式

本题含有多组数据

第一行为一个整数 $T$，表示数据组数。

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

输出格式

对于每组数据，一行一个整数，表示答案。

3
1
10
100

5
909927378
208415843

数据范围与提示

对于所有的测试点, $T \le 5, n \le 2 \times 10^5$。

• 对于 $20 \%$ 的数据, 满足 $n \le 10$
• 对于 $60\%$ 的数据, 满足 $n \le 10^3$
• 对于 $100 \%$ 的数据, 满足 $n \le 2 \times 10^5$