As Gerald, Alexander, Sergey and Gennady are already busy with the usual New Year chores, Edward hastily decorates the New Year Tree. And any decent New Year Tree must be decorated with a good garland. Edward has lamps of *m* colors and he wants to make a garland from them. That garland should represent a sequence whose length equals *L*. Edward's tree is *n* layers high and Edward plans to hang the garland so as to decorate the first layer with the first *l*<sub class="lower-index">1</sub> lamps, the second layer — with the next *l*<sub class="lower-index">2</sub> lamps and so on. The last *n*-th layer should be decorated with the last *l*<sub class="lower-index">*n*</sub> lamps, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/e444352e6f3188286a54650b0cc918121525a492.png" style="max-width: 100.0%;max-height: 100.0%;"/> 

Edward adores all sorts of math puzzles, so he suddenly wondered: how many different ways to assemble the garland are there given that the both following two conditions are met: 
 1.  Any two lamps that follow consecutively in the same layer should have different colors. 1.  The sets of used colors in every two neighbouring layers must be different. We consider unordered sets (not multisets), where every color occurs no more than once. So the number of lamps of particular color does not matter. 
Help Edward find the answer to this nagging problem or else he won't manage to decorate the Tree by New Year. You may consider that Edward has an unlimited number of lamps of each of *m* colors and it is not obligatory to use all *m* colors. The garlands are considered different if they differ in at least one position when represented as sequences. Calculate the answer modulo *p*.
The first line contains three integers *n*, *m* and *p* (1 ≤ *n*, *m* ≤ 10<sup class="upper-index">6</sup>, 2 ≤ *p* ≤ 10<sup class="upper-index">9</sup>) which are the number of the tree's layers, the number of the lamps' colors and module correspondingly. The next line contains *n* integers *l*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ 5000, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/ba00472aa4924de40da7f039202523b7f0cf35f8.png" style="max-width: 100.0%;max-height: 100.0%;"/>).
from sys import stdin #Optimiza la entrada/salida
from sys import stdout

#Ver informe para entender mejor

MAXL = 5007 #Maximo valor de la cantidad de bolas en algun piso

var = [ 0 for _ in range(MAXL)] #Guarda en la posicion j P_j^{m}
fact = [ 0 for _ in range(MAXL)] #Fuarda el factorial de cada numero menor que MAXL
layer = [[ 0 for _ in range(MAXL)] for _ in range(MAXL)] #  guarda c(i,j) en la posicion (i,j)
dp = [[ 0 for _ in range(MAXL)] for _ in range(2)] #DP desrita en el informe


n,m,p = tuple(map(int,stdin.readline().split())) #Lee la entrada

sum = 0 #valor de L
mxl = 0 #maximo valor de los l_i

l = list(map(int,stdin.readline().split()))
for i in range(n):  #Lee los l_i
    a = l[i]
    sum+=a
    mxl = max(a,mxl)

#Computa var:
var[1] = m  
for i in range(2,mxl+1):
    var[i] = (var[i-1]*(m-i+1))%p

#Computa fact:
fact[0] = 1
for i in range(1,mxl+1):
    fact[i] = (fact[i-1]*i)%p

#Calcula la funcion c de la forma descrita en el informe, para los valores menores que mxl+1
layer[0][0] = 1
for i in range(1,mxl+1):
    for j in range(1,mxl+1):
        if j > m:
            break
        layer[i][j] = (layer[i-1][j-1] + (layer[i-1][j]*(j-1))%p)%p

prv = 0 #Mantiene la suma de los valores en la ultima fila de la dp calculada
#Computa la primera fila de la dp:
for i in range(1,l[0] + 1):
    dp[0][i] = (layer[l[0]][i]*var[i])%p
    prv+=dp[0][i]
    prv%=p

for j in range(1,n):

    prv2 = 0
    pv = (j+1)%2
    ths = (j)%2

    for i in range(1,l[j] + 1):
        dp[ths][i] = ((layer[l[j]][i]*var[i])%p*prv)%p
        dp[ths][i] -= ((((layer[l[j]][i])%p*dp[pv][i])%p)*fact[i])%p
        dp[ths][i]%=p
        if dp[ths][i] < 0:
             dp[ths][i] += p
        prv2 += dp[ths][i]
        prv2%=p
    if j > 1:
        for i in range(l[j] + 1,l[j-2] +1):
            dp[ths][i] = 0
    prv = prv2
print(prv)
