题目描述

有n件彼此不同的礼物，要给m个编号不同的人，第i人恰收wi件。可以留下未送出的礼物，任意两人不能收到同一件。求方案数模P；若件数不足，输出Impossible。

本题为一本通1659的公开本地训练修订版。

输入

第一行P；第二行n m；随后m个整数wi。1≤P≤10^9，1≤n≤10^9，1≤m≤5，1≤wi≤10^9。P的每个素数幂因子均≤10^5；P=1允许。

输出

输出方案数模P，或Impossible。

输入样例

100
4 2
1
2

输出样例

12

修订说明

补模数总体上界P≤10^9与wi上界，保留每素幂≤10^5、n1e9、m5；明确礼物不同、允许剩余，由原4件送1+2件的12方案支持。