PUCMM210  A Summatory
f(n) is defined as: f(n) = 1^{3}+2^{3}+3^{3}+...+n^{3}, 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:
20160818 19:04:04
Precomputation Rocks :D 

mkfeuhrer:
20160610 17:02:15
just proper use of modulus...!! cost me a lot WA's 

akshayvenkat:
20160530 08:39:31
Last edit: 20160918 16:15:21 

KD :
20160526 12:20:53
easy one 150th AC in one :P


Nitin Sharma:
20160501 22:38:30
Same logic converted from Java to c++ passes. Hate these kind of questions. 

aloochaat1998:
20151203 16:24:19
precomputation rules :) 

Poonam:
20150711 12:44:24
Last edit: 20150711 14:22:13 

ASHUTOSH DWIVEDI:
20150629 20:36:54
few mins of paper work modular expo 0.13sec AC....... Last edit: 20150629 22:11:27 

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

r0bo_dart:
20150625 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. 
Added by:  Olson Ortiz 
Date:  20120524 
Time limit:  0.113s0.437s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Used in 2nd dominican ACMICPC Warm Up 2012 Competition in PUCMM 