## 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:32103Output:10794246`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD                 1000000003LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);

const int MAXN = 1e6+5;

ll f[MAXN];
ll pre[MAXN];

int main(){
io;
f[1] = 1;
for(ll i = 2;i <= 1000000; i++){
f[i] = (f[i - 1] + (i*i*i*1LL) % MOD) % MOD;
}
pre[1] = 1;
for(ll i = 2;i <= 1000000; i++)
pre[i] = (pre[i-1] + f[i]) % MOD;
int t;
cin >> t;
while(t--){
int n;
cin >> n;
cout << pre[n] << endl;
}
return 0;
}``````
Copy The Code &

Input

cmd
3
2
10
3

Output

cmd
10
7942
46