PUCMM210 - A Summatory


f(n) is defined as: f(n) = 13+23+33+...+n3, so it is the sum of the cubes of all natural numbers up to n.

In this problem you are about to compute,

f(1) + f(2) + f(3) + ... + f(n)

Input

The first line is an integer T (1 ≤ T ≤ 100,000), denoting the number of test cases. Then, T test cases follow.

For each test case, there is an integer n (1 ≤ n ≤ 1,000,000) written in one line.

Output

For each test case output the result of the summatory function described above.

Since this number could be very large, output the answer modulo 1,000,000,003.

Example

Input:
3
2
10
3

Output:
10
7942
46

hide comments
madhavgaba: 2016-08-18 19:04:04

Precomputation Rocks :D

mkfeuhrer: 2016-06-10 17:02:15

just proper use of modulus...!! cost me a lot WA's

KD : 2016-05-26 12:20:53

easy one 150th AC in one :P
and precomputation :P

Nitin Sharma: 2016-05-01 22:38:30

Same logic converted from Java to c++ passes. Hate these kind of questions.

aloochaat1998: 2015-12-03 16:24:19

precomputation rules :)

ASHUTOSH DWIVEDI: 2015-06-29 20:36:54

few mins of paper work modular expo 0.13sec AC.......

Last edit: 2015-06-29 22:11:27
Ankush : 2015-06-27 12:15:01

Did it using the formula, got TLE in python using raw_input(). AC using faster I/O :D

r0bo_dart: 2015-06-25 08:47:07

using a formula in the lame way will not work i guess,, coz in the formula there is a division by 60 and the mod number is not power of 10. Use precomputation.

jas.py: 2015-06-22 23:56:58

i did make a formula but got WA
used precomputation->AC

Bhuvnesh Jain: 2015-06-19 21:43:54

10 minutes of paper work... direct formula... no use of modular exponentiation or precomputation...
AC in one go


Added by:Olson Ortiz
Date:2012-05-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Used in 2nd dominican ACM-ICPC Warm Up 2012 Competition in PUCMM