All submissions for this problem are available.
When the Chef is not busy with cooking delicious foods, one of his favorite pastime is to solve mathematical problem. But as you know, he is not very good with programming. So when he fails to solve a problem he usually asks John to write a program that will solve it.
Recently the chef became interested in finding the expansion of (x1+x2+....+xk)n. Specifically he is more interested in number of terms in it. Being unable to solve the problem he asked John for help. The conversation between John and chef goes as
Chef: Can you write a program that will calculate f(n,k)= number of terms in (x1+x2+....+xk)n ?
John: That is a very easy problem.
Chef: Oh, really? Then calculate the sum over (i=0 to n) (f(i,k))
John: That is also an easy problem.
Chef: Then go finish it. And did I mention that I am calculating modulo a prime number p.
Chef: Say k=2, n=4, p=3. Then (x1+x2)4 %3 = (x14+4 x13 x2+6 x12 x22+ 4 x1 x23 + x24) %3 = (x14+ x13 x2 + x1 x23 + x24) %3. So if p=3 then f(4,2)=4.
John: OK, I am doing it.
As John started to solve the problem he realized it is not that easy. Now he asked you, his best friend, for help.
As the answer can be quite large print the output modulo 1000003.
Input file starts with a line containing a number T. T lines follow each describing a test case. Each test case consists of a line containing three space separated integers n, k, p.
Output T lines, each line containing the Sum over (i=0 to n) f(i,k) for the given prime p modulo 1000003.
p prime number
Input: 7 10 2 2 10 2 3 10 3 2 10 3 3 4 2 3 3 2 3 0 2 2 Output: 37 42 85 112 12 8 1
|Tags||feb11, medium, tanaeem|
|Time Limit:||1.28 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.