好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：BZOJ 2142

一年一度的圣诞节快要来到了。每年的圣诞节小 E 都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小 E 心目中的重要性不同，在小 E 心中分量越重的人，收到的礼物会越多。

小 E 从商店中购买了 $n$ 件礼物，打算送给 $m$ 个人，其中送给第 $i$ 个人的礼物数量为 $w_i$。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模 $P$ 后的结果。

---

输入格式

输入的第一行包含一个正整数 $P$，表示模数；

第二行包含两个正整数 $n$ 和 $m$，分别表示小 E 从商店购买的礼物数和接受礼物的人数；

以下 $m$ 行每行仅包含一个正整数 $w_i$，表示小 E 要送给第 $i$ 个人的礼物数量。

---

输出格式

若不存在可行方案，则输出 Impossible，否则输出一个整数，表示模 $P$ 后的方案数。

---

样例

样例输入

100
4 2
1
2

样例输出

12

样例解释

$n=4, m=2, w_1=1, w_2=2$。

先选出 $1$ 件礼物给第一个人，剩下 $3$ 件礼物选 $2$ 件给第二个人，最后 $1$ 件不给任何人（丢弃或自留）。
方案数为：

$$C_4^1 \times C_3^2 = 4 \times 3 = 12$$

所有 $12$ 种方案如下（设礼物编号 $1,2,3,4$）：

第一个人得一件，第二个人得两件： {1}{2,3}, {1}{2,4}, {1}{3,4}, {2}{1,3}, {2}{1,4}, {2}{3,4}, {3}{1,2}, {3}{1,4}, {3}{2,4}, {4}{1,2}, {4}{1,3}, {4}{2,3}。

---

数据范围

设 $P = p_1^{c_1} \times p_2^{c_2} \times \cdots \times p_t^{c_t}$，其中 $p_i$ 为质数。

对于 $100\%$ 的数据：

• $1 \le n \le 10^9$
• $1 \le m \le 5$
• $1 \le p_i^{c_i} \le 10^5$（每个质数幂因子模数不超过 $10^5$）
• 保证 $P \le 10^9$

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
方案数为：

$$\frac{n!}{w_1! w_2! \cdots w_m! (n - \sum w_i)!} \mod P$$

当 $n < \sum w_i$ 时无解，输出 Impossible。

由于 $P$ 不一定是质数，需要使用 扩展 Lucas 定理（或质因数分解 + CRT）：

1. 分解 $P$ 为质数幂乘积；
2. 对每个质数幂 $p^c$ 计算组合数模 $p^c$；
3. 使用中国剩余定理合并结果。

其中第二步计算 $n! \bmod p^c$ 时，需要排除 $p$ 的因子，递归处理 $n/p$ 的阶乘。