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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <cstdio>
#include "message.h"
#include "futbol.h"

using namespace std;

int n, k, p, nr, pocz, kon, dl;
long long N, K, P, L1, M1, liczba, inwersja, wynik, posredni;

long long licznik[11000005];
long long mianownik[11000005];

/*int GetN() {}
int GetK() {}
int GetP() {}
int MyNodeId() {}
void PutLL(int target, long long value) {}
void Send(int target) {}
int Receive(int source) {}
long long GetLL(int source) {}*/

long long get_inverse (long long A, long long P)
{
	long long PP = P - 2;
	long long potega = A;
	long long res = 1;
	while (PP)
	{
		if (PP % 2 == 1)
		{
			res *= potega;
			res %= P;
		}
		PP /= 2;
		potega *= potega;
		potega %= P;
	}
	return res;
}

int main ()
{
	n = GetN();
	k = GetK();
	p = GetP();
	N = (long long)(n);
	K = (long long)(k);
	P = (long long)(p);
	nr = MyNodeId();
	pocz = (k / 100) * nr;
	if (nr != 99) kon = (k / 100) * (nr + 1);
	else kon = k + 1;
	dl = kon - pocz;
	if (dl > 0)
	{
		mianownik[dl - 1] = 1;
		for (int i = dl - 2; i >= 0; --i) mianownik[i] = (mianownik[i + 1] * (long long)(pocz + i + 1)) % P;
		liczba = mianownik[0];
		if (pocz != 0)
		{
			liczba *= (long long)(pocz);
			liczba %= P;
		}
		inwersja = get_inverse(liczba, P);
		if (n != 0)
		{
			if (pocz == 0) licznik[0] = 1;
			else licznik[0] = (long long)(n - pocz + 1);
			for (int i = 1; i < dl; ++i) licznik[i] = (licznik[i - 1] * (long long)(n - pocz + 1 - i)) % P;
			for (int i = 0; i < dl; ++i)
			{
				posredni += licznik[i] * mianownik[i];
				posredni %= P;
	 		} 
		}
	}
	L1 = M1 = 1;
	if (nr != 0)
	{
		Receive(nr - 1);
		N = GetLL(nr - 1);
		L1 = GetLL(nr - 1);
		M1 = GetLL(nr - 1);
		wynik = GetLL(nr - 1);
	}
	if (dl == 0)
	{
		PutLL(nr + 1, N);
		PutLL(nr + 1, L1);
		PutLL(nr + 1, M1);
		PutLL(nr + 1, wynik);
		Send(nr + 1);
		return 0;
	}
	if (n == 0)
	{
		n = (int)(N);
		if (pocz == 0) licznik[0] = 1;
		else licznik[0] = (long long)(n - pocz + 1);
		for (int i = 1; i < dl; ++i) licznik[i] = (licznik[i - 1] * (long long)(n - pocz + 1 - i)) % P;
		for (int i = 0; i < dl; ++i)
		{
			posredni += licznik[i] * mianownik[i];
			posredni %= P;
 		} 
	}
	posredni *= L1;
	posredni %= P;
	L1 *= licznik[dl - 1];
	L1 %= P;
	M1 *= inwersja;
	M1 %= P;
	posredni *= M1;
	posredni %= P;
	wynik += posredni;
	wynik %= P;
	if (nr != 99)
	{
		PutLL(nr + 1, N);
		PutLL(nr + 1, L1);
		PutLL(nr + 1, M1);
		PutLL(nr + 1, wynik);
		Send(nr + 1);
		return 0;
	}
	printf("%lld\n", wynik);
	return 0;
}