Integral Calculus
TimeLimit:3500MS MemoryLimit:532768KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description
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 \cdot P^{-1}$ mod ($10^9$+9). Here $P^{-1}$ is multiplicative inverse of P modulo $10^9$+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 \cdot P^{-1}$ mod ($10^9$+9). Here $P^{-1}$ is multiplicative inverse of P modulo $10^9$+9.
Input
The first line of the input contains a single integer T(1≤T≤$10^5$), the number of test cases.
Each of the next T lines contains an integer N(1≤N≤$10^5$ ), which is described above.
Each of the next T lines contains an integer N(1≤N≤$10^5$ ), which is described above.
Output
For each test case, you should print the answer in a single line.
SampleInput
1 1
SampleOutput
400000006