记录编号	26938	评测结果	AAAAAAAAAA
题目名称	sumcount	最终得分	100
用户昵称	老虎小飞	是否通过	通过
代码语言	Pascal	运行时间	2.579 s
提交时间	2011-07-29 18:20:27	内存使用	45.89 MiB

var
p,pre,num:array[0..2000000]of int64;
n,m,a,b,i,j,q,t:longint;
ans,ans0:int64;

function ksm(a,k:int64):int64;
var
kk:int64;
begin
    if k=0 then exit(1);
    if k=1 then exit(a);
    kk:=ksm(a,k div 2);
    kk:=kk*kk;
    if odd(k) then kk:=kk*a;
    exit(kk);
end;

function min(a,b:int64):int64;
begin
    if a>b then exit(b);
    exit(a);
end;

function cc(m,n:int64):int64;
var
i:longint;
a,b,c:int64;
begin
    fillchar(num,sizeof(num),0);
    a:=min(m,n-m);
    b:=n-a;
    c:=1;
    for i:=2 to a do num[i]:=-1;
    for i:=n downto b+1 do begin
        if pre[i]=0 then begin
            c:=c*ksm(i,num[i]+1);
            if c>q*10 then c:=c mod q;
        end
        else begin
            inc(num[i]);
            inc(num[pre[i]],num[i]);
            inc(num[i div pre[i]],num[i]);
        end;
    end;
    for i:=b downto 2 do begin
        if pre[i]=0 then begin
            c:=c*ksm(i,num[i]);
            if c>q*10 then c:=c mod q;
        end
        else begin
            //inc(num[i]);
            inc(num[pre[i]],num[i]);
            inc(num[i div pre[i]],num[i]);
        end;
    end;
    exit(c);
end;

begin
assign(input,'sumcount.in');reset(input);
assign(output,'sumcount.out');rewrite(output);
    read(n,a,b,q);
    for i:=2 to b+n do begin
        if pre[i]=0 then begin
            inc(t);p[t]:=i;
        end;
        for j:=1 to t do begin
            if i*p[j]>b+n then break;
            pre[i*p[j]]:=p[j];
            if i mod p[j]=0 then break;
        end;
    end;
    ans:=cc(n,b+n);
    if a>0 then ans0:=cc(n,a+n-1)
    else ans0:=0;
    writeln((ans-ans0+q) mod q);
close(input);close(output);
end.