该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

无额外样例。

题目描述

有 N 个不同的苹果，要从中选择若干个放到 M 个不同的盘子里，其中第 i 个盘子里要求放入 Ai 个苹果。

问：有多少种不同的放置方案？

答案可能很大，你需要将其 mod K 后输出。如果不存在合法的放置方案，则输出 -1

输入

第一行：三个整数 N, M, K

第二行：M 个整数 Ai

输出

一个整数，表示答案。

样例1输入

5 2 10000
1 3

样例1输出

20

样例2输入

123456789 5 9876543
123 233 3456 789 1234567

样例2输出

8658234

数据范围

设 $K = \prod_{i=1}^{t} p_i ^ {c_i}$，其中 $p_i$ 为质数。输入数据保证 $1≤p_i^{c_i} ≤ 10^5$。

100%的数据：$1≤N≤10^9, 1≤M≤5, 0 ≤ A_i ≤ K ≤ 10^9$

其中有 15% 的数据，$N ≤ 15, M ≤ 5$

在剩下的 85% 数据中，约有 60% 的数据满足 $t ≤ 2, c_i = 1, p_i ≤ 10^5$，约有 30% 的数据满足 $p_i​ ≤ 200$。