记录编号	168283	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]礼物(魏铭)	最终得分	100
用户昵称	RP++	是否通过	通过
代码语言	C++	运行时间	0.154 s
提交时间	2015-07-03 09:19:55	内存使用	0.31 MiB

#include <iostream>
#include <cstdio>

using namespace std;

#define LL long long

int a[50], b[50], c[50], d[50];
LL ans, tim;

int Quick_Pow(LL a, int b, int p) {
	LL ans = 1;
	while(b) {
		if(b&1) (ans *= a) %= p;
		b >>= 1, (a *= a) %= p;
	}
	return ans;
}

void exgcd(int a, int b, LL &x, LL &y) {
	if(b == 0) {
		x = 1, y = 0;
	} else {
		exgcd(b, a % b, x, y);
		LL tmp = x;
		x = y, y = tmp - (a / b) * y;
	}
}

void fact(int n, int i) {
	LL tmp = 1;
	for(int j = 2; j < d[i]; j++) if(j % a[i] != 0)
		(tmp *= j) %= d[i];
	(ans *= Quick_Pow(tmp, n / d[i], d[i])) %= d[i];
	for(int j = n % d[i]; j >= 2; j--) if(j % a[i] != 0)
		(ans *= j) %= d[i];
	tim += n / a[i];
	if(n > a[i]) fact(n / a[i], i);
}

int getc(int n, int m, int i) {
	LL p, q, now = 0;
	ans = 1, tim = 0, fact(n, i);
	p = ans, now += tim;
	ans = 1, tim = 0, fact(m, i);
	q = ans, now -= tim;
	ans = 1, tim = 0, fact(n - m, i);
	(q *= ans) %= d[i], now -= tim;
	if(now >= b[i]) return 0;
	LL x, y;
	exgcd(q, d[i], x, y);
	if(x < 0) x += d[i];
	return p * Quick_Pow(a[i], now, d[i]) * x % d[i];
}

LL solve(int n, int m) {
	for(int i = 1; i <= a[0]; i++)
		c[i] = getc(n, m, i);
	int last = d[1]; LL x, y;
	for(int i = 2; i <= a[0]; i++) {
		exgcd(last, d[i], x, y);
		if(y < 0) y += last;
		last *= d[i], (y *= c[i] - c[i - 1]) %= last, c[i] = (-y * d[i] + c[i]) % last;
	}
	return c[a[0]];
}

int main() {
	freopen("nt2011_gift.in", "r", stdin);
	freopen("nt2011_gift.out", "w", stdout);
	int n, m, p;
	scanf("%d%d%d", &p, &n, &m);
	int tmp = p;
	for(int i = 2; i * i <= tmp; i++) if(tmp % i == 0) {
		a[++a[0]] = i;
		while(tmp % i == 0) {
			b[a[0]]++, tmp /= i;
		}
	}
	if(tmp > 1) a[++a[0]] = tmp, b[a[0]] = 1;
	for(int i = 1; i <= a[0]; i++) d[i] = Quick_Pow(a[i], b[i], p + 1);
	LL ans = 1;
	for(int i = 1, x; i <= m; i++) {
		scanf("%d", &x);
		if(n >= x) (ans *= solve(n, x)) %= p;
		else {
			printf("Impossible\n"); return 0;
		}
		n -= x;
	}
	printf("%lld\n", (ans + p) % p);
}