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
#include <cstdio>
#include <algorithm>
#define scanf(...) scanf(__VA_ARGS__)?:0
using namespace std;
typedef long long ll;
#ifdef LOCAL
int initialized,_n,_k,_p,_id,_num;
void init() {
	initialized=1;
	printf("n, k, p, id, num: ");
	scanf("%d%d%d%d%d",&_n,&_k,&_p,&_id,&_num);
}
int GetN() {
	if (!initialized) init();
	return _n;
}
int GetK() {
	if (!initialized) init();
	return _k;
}
int GetP() {
	if (!initialized) init();
	return _p;
}
int MyNodeId() {
	if (!initialized) init();
	return _id;
}
int NumberOfNodes() {
	if (!initialized) init();
	return _num;
}
void PutInt(int target,int value) {
	printf("PutInt %d to %d\n",value,target);
}
void PutLL(int target,ll value) {
	printf("PutLL %lld to %d\n",value,target);
}
void Send(int target) {
	printf("Send to %d\n",target);
}
int GetInt(int source) {
	int ret;
	printf("GetInt from %d: ",source);
	scanf("%d",&ret);
	return ret;
}
ll GetLL(int source) {
	ll ret;
	printf("GetLL from %d: ",source);
	scanf("%lld",&ret);
	return ret;
}
void Receive(int source) {
	printf("Receive from %d\n",source);
}
#else
#include "futbol.h"
#include "message.h"
#endif
int n,k,p,id,num;
ll pot(ll a,ll b) {
	ll ret=1;
	while (b) {
		if (b&1) ret=ret*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ret;
}
int main() {
	n=GetN();
	k=GetK()+1;
	p=GetP();
	id=MyNodeId();
	num=NumberOfNodes();
	int zakres=k/num+1;
	int pocz=id*zakres;
	int kon=min(k,(id+1)*zakres);
	int len=kon-pocz;
	ll *odw,suma=0,zm=1;
	if (len<=0) goto skip;
	
	odw=(ll*)malloc((len+1)*sizeof(ll));
	odw[0]=1;
	for (int i=1; i<=len; i++) odw[i]=odw[i-1]*(i+pocz)%p;
	odw[len]=pot(odw[len],p-2);
	for (int i=len-1; i>=0; i--) odw[i]=odw[i+1]*(i+pocz+1)%p;
	
	for (int i=pocz; i<kon; i++) {
		suma=(suma+zm*odw[i-pocz])%p;
		zm=zm*(n-i)%p;
	}
	zm=zm*odw[len]%p;
	free(odw);
	
	skip:
	
	if (id!=0) {
		PutInt(0,(int)suma);
		PutInt(0,(int)zm);
		Send(0);
	} else {
		for (int i=1; i<num; i++) {
			Receive(i);
			int s=GetInt(i);
			int z=GetInt(i);
			suma=(suma+zm*s)%p;
			zm=zm*z%p;
		}
		printf("%lld\n",suma);
	}
}