Description

一年一度的圣诞节快要来到了. 每年的圣诞节小 E 都会收到许多礼物, 当然他也会送出许多礼物. 不同的人物在小 E 心目中的重要性不同, 在小 E 心中分量越重的人, 收到的礼物会越多. 小 E 从商店中购买了 \(n\) 件礼物, 打算送给 \(m\) 个人, 其中送给第 \(i\) 个人礼物数量为 \(w_i\). 请你帮忙计算出送礼物的方案数 (两个方案被认为是不同的, 当且仅当存在某个人在这两种方案中收到的礼物不同). 由于方案数可能会很大, 你只需要输出模 \(P\) 后的结果.

Input

输入的第一行包含一个正整数 \(P\), 表示模;

第二行包含两个整数 \(n, m\), 分别表示小 E 从商店购买的礼物数和接受礼物的人数;

以下 \(m\) 行每行仅包含一个正整数 \(w_i\), 表示小 E 要送给第 \(i\) 个人的礼物数量.

Output

若不存在可行方案, 则输出 Impossible, 否则输出一个整数, 表示模 \(P\) 后的方案数.

Sample Input

100
4 2
1
2

Sample Output

12

Data Range

设 \(P = p_1^{c_1} \cdot p_2^{c_2} \cdot p_3^{c_3} \cdot \ldots \cdot p_t^{c_t}\),\(p_i\) 为质数.

对于所有数据, 满足:\(1 \leq n \leq 10^9, 1 \leq m \leq 5, 1 \leq p_i^{c_i} \leq 10^5\)

Explanation

此题很难 (我数学不好...... )

传送门:http://blog.csdn.net/popoqqq/article/details/39891263

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
typedef pair<lli,lli> prll;
const int maxn = 10, maxp = 110;

struct factor {
    lli p, a, p_a, rem;
} prime[maxp];
int pcnt;

void decomposition(lli x)
{
    for (lli i = 2; i*i <= x; i++) if (x % i == 0) {
        prime[++pcnt].p = i;
        prime[pcnt].p_a = 1;
        while (x % i == 0)
            x /= i, prime[pcnt].a += 1, prime[pcnt].p_a *= i;
    }
    if (x != 1)
        prime[++pcnt].p = x, prime[pcnt].a = 1, prime[pcnt].p_a = x;
    return ;
}

lli pwr(lli x, lli y, lli modr)
{
    lli res = 1;
    for (lli i = 1; i <= y; i <<= 1, x = x*x % modr)
        if (y & i)
            res = res * x % modr;
    return res;
}

prll deal(lli x, int pos)
{
    factor& prm = prime[pos];
    prll res = make_pair(1ll, x / prm.p);
    for (lli i = 1; i < prm.p_a; i++)
        if (i % prm.p != 0)
            res.first = res.first * i % prm.p_a;
    res.first = pwr(res.first, x / prm.p_a, prm.p_a);
    for (lli i = x - x % prm.p_a + 1; i <= x; i++)
        if (i % prm.p != 0)
            res.first = res.first * i % prm.p_a;
    if (res.second) {
        prll tmp = deal(res.second, pos);
        res.first = res.first * tmp.first % prm.p_a;
        res.second += tmp.second;
    }
    return res;
}

prll extended_gcd(lli x, lli y)
{
    if (!y) return make_pair(1ll, 0ll);
    prll tmp = extended_gcd(y, x % y);
    return make_pair(tmp.second, tmp.first - x / y * tmp.second);
}

lli reverse(lli x, lli modr)
{
    lli res = extended_gcd(x, modr).first;
    res = (res % modr + modr) % modr;
    return res;
}

lli n, m, sum;
lli modr, a[maxn];

int main(int argc, char** argv)
{
    scanf("%lld%lld%lld", &modr, &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%lld", &a[i]);
        sum += a[i];
    }
    // That wasn't even possible because we demanded more
    if (n < sum) {
        printf("Impossible\n");
        return 0;
    }
    // We had to fill another extra region for the exceeded
    if (n > sum)
        a[++m] = n - sum;
    // Decompositing modr...
    decomposition(modr);
    // Calculating moduli
    for (int i = 1; i <= pcnt; i++) {
        prll tmp = deal(n, i);
        for (int j = 1; j <= m; j++) {
            prll tmp2 = deal(a[j], i);
            tmp.second -= tmp2.second;
            tmp.first = tmp.first * reverse(tmp2.first, prime[i].p_a) % prime[i].p_a;
        }
        tmp.first *= pwr(prime[i].p, tmp.second, prime[i].p_a);
        prime[i].rem = tmp.first % prime[i].p_a;
    }
    // Chinese remainder theorem
    lli res = 0;
    for (int i = 1; i <= pcnt; i++) {
        prll tmp = extended_gcd(modr / prime[i].p_a, prime[i].p_a);
        lli x = (tmp.first % modr + modr) % modr;
        res += x * modr / prime[i].p_a * prime[i].rem;
        res %= modr;
    }
    res = (res % modr + modr) % modr;
    // Output
    printf("%lld\n", res);
    return 0;
}