已知以下泰勒展开:
ex=∑n=0∞xnn!,x∈Re^{x}=\sum_{n=0}^{\infty}{\frac{x^{n}}{n!}},x\in Rex=n=0∑∞n!xn,x∈R
计算满足以下条件的字符串个数,答案对 109+710^9+7109+7 取模:
S
C
N
U
输入
多组测试用例。第一行一个整数 T (1≤T≤106)T \ (1 \leq T \leq 10^6)T (1≤T≤106),表示测试用例数。
接下来 TTT 行每行一个整数 n (1≤n≤109)n \ (1 \leq n \leq 10^9)n (1≤n≤109)。
输出
输出 TTT 行,每行一个整数,表示一组测试用例的答案。
样例
2 1 4
2 72
提示
建议使用较为高效的输入输出方式。