题目描述

探险队在探险途中先后遇到了k个洞窟。出发时探险队有n人，在第i个洞窟，探险队派出$x_i$人进入洞窟探险。问派去洞窟探险的人员分配方案有多少种？因为答案可能会很大，所以只需输出答案除以p的余数。

例如：探险队有4人，遇到了2个洞窟，先后派出1,2个人探索，那么人员分配方案有以下12种

(1)(2,3)；(1)(2,4)；(1)(3,4)；(2)(1,3)；(2)(1,4)；(2)(3,4)；

(3)(1,2)；(3)(1,4)；(3)(2,4)；(4)(1,2)；(4)(1,3)；(4)(2,3)；

输入格式

第1行，3个正整数n,k,$p_n$,k,p

第2行，kk个正整数$x_{1}$,$x_{2}$,⋯,$x_k$

输出格式

输出人员分配方案数除以p的余数。

数据范围与约定

$1\le n\le 2000$；$1\le k\le 50$；$2\le p\le 10^{9}$；

$1\le \sum x_i\le n$。

可见测试数据

输入数据 1

4 2 10007
1 2

输出数据 1

12

输入数据 2

6 1 743
3

输出数据 2

20

输入数据 3

6 3 7
2 2 1

输出数据 3

5