The powerful sum

Problem code: C2

All submissions for this problem are available.

Let us calculate the sum of k-th powers of natural numbers from 1 to n. As the result can be quite large, output the result modulo some integer p.

Input

First t<=10 - the number of test cases.
Each test case consist of numbers: 1<=n<=1000000000, 1<=k<=100, 1<=p<=1000000000.

Output

For each test case, output the value: (1k+2k+...+nk) mod p.

Example

For input:

4
10 1 1000000
10 2 1000000
10 3 1000000
10 4 1000000

the correct output is:

55
385
3025
25333
Date: 2009-04-20
Time limit: 2s
Source limit: 50000
Languages: C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp HASK CAML CLPS PRLG WSPC BF ICK TEXT


Comments

donpaul @ 3 May 2009 04:10 AM

the question looks simple.. but the chef is putting a hell of a test case it seems.. :)

chang @ 3 May 2009 07:10 AM

yup...the huge test case is the only prblm to solve here :|

mohitkanwal @ 4 May 2009 05:11 AM

anybody knows wat's the meaning of runtime error (SIGARBT)

kiran_19_6 @ 4 May 2009 04:36 PM

# include
#include
int powerOfN(int n, int k);

int main(){

int n, k,p ;
int result =0;
int i=0;

printf("\n Enter N:");
scanf("%d",

donpaul @ 6 May 2009 08:42 PM

surprisd that nobody has submitted in C ?? is thr any reason for that??

aditya @ 7 May 2009 10:28 PM

obviously the test case would be n=10^9,k=100,p=10^9

sid_chilling @ 15 May 2009 03:25 AM

No one seems to have submitted in Java so far. Any particular reasons for that? All my submissions get timed out when I program in Java. But the same logic runs fine with C . What is the reason?

prunthaban @ 15 May 2009 01:55 PM

@Siddharth My solution during the contest was in Java.

yellow_agony @ 20 May 2009 01:21 AM

can i not submit

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions