题目描述

有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方案支持。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：补模数总体上界P≤10^9与wi上界，保留每素幂≤10^5、n1e9、m5；明确礼物不同、允许剩余，由原4件送1+2件的12方案支持。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1659。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。