Problem Description
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 aiis 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.
Input
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 ai.
Input ends with n=k=p=0.
Output
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.
Sample Input
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
Sample Output
38
3
4
0
748
4035
