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
#include <bits/stdc++.h>
#include "futbol.h"
#include "message.h"
#include <bits/stdc++.h>                                                        
using namespace std;                                                                                                                    
typedef long long ll;                                                           
typedef pair<int, int> Pii;                                                     
typedef vector<Pii> vpii;                                                       
typedef vector<int> vi;                                                         
typedef vector<ll> vll;                                                         
#define pb push_back                                                            
#define fst first                                                               
#define snd second
//int GetN() { return 1e9; }
//int GetK() { return 500000000; }
//int GetP() { return 1000000000 + 7;}
//int GetElement(int i) { return 1e6; }
int nodes;
int ja;
ll n;
ll k;
ll p;
bool fliped;
void init()
{
	nodes =  NumberOfNodes();
	ja = MyNodeId();
	n = GetN();
	k = GetK();
	p = GetP();
	if(n - k - 1 < k)
	{
		k = n - k - 1;
		fliped = true;
	}
}

void wyslij(int x, vll V)
{
	for(ll y : V)
	{
		PutLL(x, y);
		//printf("Wysylam %lld\n", y);
	}
	Send(x);
}
vll odbierz(int x, int ile)
{
	vll res;
	Receive(x);
	for(int i = 0; i < ile; ++i)
	{
		res.pb(GetLL(x));
		//printf("Odbieram %lld\n", res.back());
	}
	return res;
}
ll pot(ll x, ll exp)
{
	ll res = 1;
	while(exp)
	{
		if(exp & 1)
			res = res * x % p;
		x = x * x % p;
		exp >>= 1;
	}
	return res;
}
ll rev(ll x)
{
	return pot(x, p-2);
}

int main()
{
	init();
	ll res = 0;
	ll b = 1ll * ja * (k+1) / nodes;
	ll e = 1ll * (ja + 1) * (k+1) / nodes;
	//printf("b = %lld e = %lld\n", b, e);
	ll suma = 0;
	ll cur = 1;
	vll chuj;
	ll sil = 1;
	for(ll i = b; i < e; ++i)
	{ // rano przerobić, żeby zapierdalało
		chuj.pb(cur);
		sil = sil * (i + 1) % p;
		///cur = cur * (n - i) % p * rev(i + 1) % p;
		cur = cur * (n - i) % p;
	}
	sil = rev(sil);
	cur = cur * sil % p;
	for(int i = e - 1; i >= b; --i)
	{
		sil = sil * (i + 1) % p;
		suma += chuj.back() * sil % p;
		chuj.pop_back();
	}
	
	//printf("cur = %lld\n", cur);
	if(ja == 0)
	{
		for(int i = 1; i < nodes; ++i)
		{
			vll v = odbierz(i, 2);
			suma += cur * v[0] % p;
			cur = cur * v[1] % p;
		}
		if(fliped)
		{
			suma = (pot(2, n) - suma % p + p) % p;
		}
		printf("%lld\n", suma % p);
	}
	else
	{
		wyslij(0, {suma % p, cur});
	}
}