1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include "message.h"
#include "futbol.h"
#include <iostream>

using namespace std;

long long n, k, p;
long long wynik;

long long silnie[101];

long long potModulo(long long x, long long c, long long mod) {
	if(c == 0)
		return 1;
	if(c % 2 == 1)
		return (x * potModulo(x, c - 1, mod)) % mod;

	long long t = potModulo(x, c / 2, mod);
	return (t * t) % mod;
}

long long obliczSilnie(long long x) {
	long long wynik = silnie[x / (10 * 1000 * 1000)];
	for(int i = x / (10 * 1000 * 1000) + 1; i <= x; i++) {
		wynik = (wynik * i) % p;
	}
	return wynik;
}

int main()
{
	n = GetN();
	k = GetK();
	p = GetP();

	long long silnia = 1;

	for(int i = 10 * 1000 * 1000 * MyNodeId() + 1; i <= 10 * 1000 * 1000 * (MyNodeId() + 1); i++) {
		silnia = (silnia * i) % p;
	}

	silnie[0] = 1;
	silnie[1] = silnia;

	if(MyNodeId() != 0) {
		PutLL(0, silnia);
		Send(0);
	}
	else {
		for(int i = 1; i < NumberOfNodes(); i++) {
			Receive(i);
			silnie[i + 1] = (silnie[i] * GetLL(i)) % p;
		}

		long long silniaN = obliczSilnie(n);
		long long silniaK = obliczSilnie(k);
		long long silniaNMK = obliczSilnie(n - k);

		long long silniaKOdwrotnosc = potModulo(silniaK, p - 2, p);
		long long silniaNMKOdwrotnosc = potModulo(silniaNMK, p - 2, p);


		for(int i = k; i >= 0; i--) {
			wynik = (wynik + (((silniaN * silniaKOdwrotnosc) % p) * silniaNMKOdwrotnosc) % p) % p;
			silniaKOdwrotnosc = (silniaKOdwrotnosc * i) % p;
			silniaNMKOdwrotnosc = (silniaNMKOdwrotnosc * potModulo(n - i + 1, p - 2, p)) % p;
		}

		cout << wynik;

	}

    return 0;
}