|
||||||||||
Integral CalculusTime Limit: 7000/3500 MS (Java/Others) Memory Limit: 532768/532768 K (Java/Others)Total Submission(s): 76 Accepted Submission(s): 28 Problem Description Ely has just faced a complicated math problem. So she now needs assistance of you ¨C 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. 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. Output For each test case, you should print the answer in a single line. Sample Input
Sample Output
Source | ||||||||||
|