Algorithm

problem link- https://www.spoj.com/problems/PUCMM210/

PUCMM210 - A Summatory

#ad-hoc-1 #math-6

 

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

 

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 & Try With Live Editor

Input

x
–
+
cmd
3
2
10
3

Output

x
–
+
cmd
10
7942
46
Advertisements

Demonstration

SPOJ Solution-A Summatory-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python