[BeiJingWc2008]Gate Of Babylon

《吉尔伽美什史诗》是人类历史上第一部英雄史诗，也是两河流域最杰出的文学作品之一。作品讲述了吉尔伽美什一生的传奇故事。在动画《Fate/stay night》中，吉尔伽美什与亚瑟王等传说中的英雄人物一同出现在现实世界，展开了一场惊天动地的战斗。

在记载于 $12$ 块泥板的史诗中，吉尔伽美什与同伴恩奇都一起降伏了森林的守护者——神兽洪巴巴，成为地上最强的王者，并将世间所有财宝收入囊中。王之财宝（Gate of Babylon）也因此成为吉尔伽美什炫耀的资本。

一天，吉尔伽美什突发奇想：如果从自己无尽的财宝中任意选出不超过 $M$ 件宝具，一共有多少种搭配方案？

假设他共有 $N$ 种不同类型的宝具。大部分类型的宝具数量无限，但其中有 $T$ 种超级神器的数量有限，第 $i$ 种超级神器最多只能选择 $B_i$ 件。

如果两种搭配方案中，每种类型的宝具数量都相同，则认为它们是同一种方案。

由于方案数可能很大，吉尔伽美什选择了一个质数 $P$。请计算方案总数对 $P$ 取模后的余数。注意，一件宝具也不选择同样是一种方案。

输入格式

第一行包含 $4$ 个整数 $N,T,M,P$，分别表示宝具类型总数、数量有限的超级神器类型数、最多可选择的宝具总数和用于取模的质数。

接下来 $T$ 行，每行包含一个整数 $B_i$，表示第 $i$ 种超级神器最多可选择的数量。

输出格式

输出一个整数，表示方案总数对 $P$ 取模后的余数。

样例输入

2 1 10 13
3

样例输出

12

数据范围

• $N,M\le 10^9$；
• $P\le 10^5$，且 $P$ 为质数；
• $B_i\le 10^9$；
• $0\le T\le N$；
• $M>0$；
• $B_i>0$；
• $T\le 15$。

来源与许可

本题为北京冬令营 2008 试题「Gate Of Babylon」，题面与测试数据整理自 BZOJ。

样例 1

输入

2 1 10 13
3

输出

12