找规律后可以之后答案就是

k^(m-1)*(n-(m-1)*k)+(m+(m-1)*k+1)*k^(m-1) div 2

/**************************************************************    Problem: 3142    User: BLADEVIL    Language: Pascal    Result: Accepted    Time:0 ms    Memory:224 kb****************************************************************/ //By BLADEVILvar    n, m                    :int64;    k, p, x                 :int64;     function mi(a,b:int64):int64;var    sum, ans                :int64;begin    sum:=a; ans:=1;    while b>0 do    begin        if b mod 2=1 then ans:=ans*sum mod p;        sum:=sum*sum mod p;        b:=b div 2;    end;    exit(ans);end;begin    readln(n,k,m,p);    dec(k);    x:=mi(m,k-1);     writeln(int64(n mod p*m-m*(m+1) div 2 mod p*k+p*1000000000) mod p*x mod p);end.