The Diary of Math Teacher

03/21/2010 SUN Sunny

“Hi, boys and girls ,today we will learn the “Deference” .”
“What is the “Deference”? Is that difficult? ”
“Boys , don’t worry, and you will know it immediately.”


“f(x) is an function, and x is an integer. Δf( x ) = f (x + 1 ) – f( x ) ”
“In general, Δ(n+1)f( x ) = Δ(n)f( x+1 ) - Δ(n)f( x )”
“In particular, Δ(0)f( x ) = f( x )，Δ(1)f( x ) = Δf (x )”


“Do you understand?”
“No!!!!!!!!!!!!”
“Does anyone understand?”
“Only you our teacher!”
“How dare you be so ironic. Since you all have learnt the Factorial. I will give you a problem of factorial and difference. Anyone who can’t solve it will be severely punished”


“ The problem is:
Given a nonnegative integer array {a[n]} , and each of its elements a[i] (1<=i<=n)is also known.
f(x)=∏{1<=i<=n}(x+a[i])
Your task is to calculate Δ(k)f(0)/k! ”
Damn it,really bad mood. Well, I'd better go to sleep now.

Multiple test cases.
The first line of each test case will be 3 integers : n(1<=n<=1000) , k(0<=k<=n-1) , p(1<=P<=20000).
The following line will contain n integers a[i] (0<=a[i]<=20000).
Input ends with n=k=p=0.

For each test case ,pint the answer mod p in one separate line.
The last case n=k=p=0 does not need to be processed.

5 3 20000
1 0 0 1 0
5 3 7
1 0 1 0 0
3 1 7777
1 1 0
3 0 94
0 1 1
7 4 10000
0 1 0 3 0 1 0
16 12 17595
4898 287 4879 598 5927 8 764 57 233 188 58 97 899 9876 47 323
0 0 0

38
3
4
0
748
4035

In the first test case:
f( x ) = ∏{1<=i<=5}(x + a[i]) = (x + a[1])(x + a[2])(x + a[3])(x + a[4])(x + a[5]) = (x + 1)*x*x*(x + 1)*x

So , f(0) = 0 , f(1) = 4 , f(2) = 72 , f(3) = 432
Δf(0) = 4 , Δf(1) = 68 , Δf(2) = 360
Δ(2)f(0) = 64 , Δ(2)f(1) = 292
Δ(3)f(0) = 228
3! = 1*2*3 = 6
228/6 = 38

2010 ACM-ICPC Multi-University Training Contest（2）——Host by BUPT