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
omar alkattan: 2013-10-25 00:47:50

AC :)
Be careful about modulo in subtracting

BLANKRK: 2013-09-23 20:38:35

huhh.. finaly done!!

Sanchit Manchanda: 2013-08-02 05:55:54

Getting SIGSEGV for this code. Any idea whats wrongs.
<snip>

Last edit: 2022-07-12 22:49:12
***: 2013-07-22 17:43:59

ans for n=1000000?

shiv prasad chabarval: 2013-06-23 18:27:22

mod caused 11 WA's... huh AC with a very bad timing 2.02.

Gaurav Khewal: 2013-06-16 16:03:30

my century!!!!

rafiki93: 2013-05-18 08:51:14

can you please give some big number test cases.have used mod literally everywhere but still getting wrong ans

yaswanth: 2013-05-01 16:36:11

very simple!! similar to http://www.spoj.com/problems/SUMPOWK1/

Arika Saputro: 2013-04-30 02:46:40

i reduce from 11 branch to 2 branch and the time only reduced by 0.01 =(

[Lakshman]: 2013-04-03 06:31:21

finally AC after several TLE,used precomputation to pass the time limit.


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