记录编号	26911	评测结果	AAAAAAAAAA
题目名称	sumcount	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	1.618 s
提交时间	2011-07-29 16:03:00	内存使用	15.52 MiB

#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN=2000005;
int MO;
typedef long long Int;
typedef pair<int,int> Pair;
#define pb push_back
#define mp make_pair

int powmod(Int x,int n)
{
	x=x%MO;
	Int y=n%2?x:1;
	while(n>>=1)
	{
		x=x*x%MO;
		if (n%2)
			y=y*x%MO;
	}
	return y;
}

int N,M,A,B,tot;
int flag[MAXN],mul[MAXN];

int getans(int x)
{
	if (x<0)
		return 0;
	int ret=1;
	M=x+N;
	for(int i=2;i<=M;i++)
		flag[i]=1;
	for(int i=2;i<=M;i++)
		if (flag[i]==1)
			for(int j=i+i;j<=M;j+=i)
				flag[j]=i;
	for(int i=2;i<=M;i++)
		mul[i]=1;
	for(int i=2;i<=N;i++)
		mul[i]--;
	for(int i=2;i<=M-N;i++)
		mul[i]--;
	for(int i=M;i>=2;i--)
		if (flag[i]!=1)
		{
			mul[flag[i]]+=mul[i];
			mul[i/flag[i]]+=mul[i];
			mul[i]=0;
		}
		else
			ret=(Int)ret*powmod(i,mul[i])%MO;
	return ret;
}

int main()
{
	freopen("sumcount.in","r",stdin);
	freopen("sumcount.out","w",stdout);
	scanf("%d%d%d%d",&N,&A,&B,&MO);
	printf("%d\n",(getans(B)-getans(A-1)+MO)%MO);
	return 0;
}