题目描述

《基尔伽美修》是人类历史上第一部英雄史诗，两河流域最杰出的文学作品之一。作品讲述了基尔伽美修一生的传奇故事。在动画 Fate/stay night 中，基尔伽美修与亚瑟王等传说中的英雄人物一起出现在了现实世界，展开了一场惊天地、泣鬼神的战斗。在记载于 $12$ 块泥板的史诗中，基尔伽美修与同伴安吉杜一起降伏了森林的守护者——神兽洪芭芭，成为地上最强的王者，同时将世间所有财宝收归手中。王之财宝 (Gate of Babylon) 成为 Fate 中金皮卡（基尔伽美修的外号…）炫耀的资本……

一天金皮卡突发奇想：如果从自己无尽的财宝里面，随便抽不超过M件宝具出来砸死敌人的话。一共有多少种搭配方法呢？假设金皮卡一共有N种不同类型的宝具，大部分类型的宝具都有无限多，但其中T种超级神器的数量是有限的。设第i种超级神器的数量不超过 $B_i$ 件。若相同类型的宝具数量相同，则认为是相同的搭配方案。

金皮卡知道方案数会很大，从小数学成绩就好的他挑选了一个质数 $P$，请你帮他计算一下方案数模 $P$ 后的余数。注意，一件也不选也是一种方案。

输入格式

第一行包含 $4$ 个整数，分别为 $N,T,M,P$

之后 $T$ 行，每行一个整数，代表 $B_i$

$N,M \leq 10^9,~P \leq 10^5,~B_i \leq 10^9$

$0 \leq T \leq N,~M>0.~B_i>0,~T \leq 15$

输出格式

仅包含一个整数，即方案数模 $P$ 后的余数。

2 1 10 13
3

12

样例说明

只有一种超级神器，数量不超过 $3$。

当不选择超级神器时，另一种宝具可以挑选 $0$ 到 $10$ 件，共 $11$ 种方案。

当选择 $1$ 件神器出来时，另一种宝具可以挑选 $0$ 到 $9$ 件，共 $10$ 种方案。

当挑选 $2$ 件神器时，共 $9$ 种方案。

挑选 $3$ 件神器时，共 $8$ 种方案。

一共有 $11+10+9+8=38$ 种方案，$38\bmod13=12$，于是答案等于12