7441: Integral Calculus
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
Ely has just faced a complicated math problem. So she now needs assistance of you – a talented programmer. The problem is as below.
Given a positive integer N, calculate the following value:
We can prove that it is a rational number. Let’s denote it by Q/P, where gcd(P,Q)=1 and P,Q>0. Since these numbers can be very huge for large N, you are only to print the value Q⋅P−1 mod (109+9). Here P−1 is multiplicative inverse of P modulo 109+9.
Given a positive integer N, calculate the following value:
We can prove that it is a rational number. Let’s denote it by Q/P, where gcd(P,Q)=1 and P,Q>0. Since these numbers can be very huge for large N, you are only to print the value Q⋅P−1 mod (109+9). Here P−1 is multiplicative inverse of P modulo 109+9.
输入格式
The first line of the input contains a single integer T(1≤T≤105), the number of test cases.
Each of the next T lines contains an integer N(1≤N≤105 ), which is described above.
Each of the next T lines contains an integer N(1≤N≤105 ), which is described above.
输出格式
For each test case, you should print the answer in a single line.
输入样例 复制
1
1输出样例 复制
400000006