bzoj3142

百度空间发公式太累，给个比较详细的解题链接吧
http://www.cnblogs.com/jianglangcaijin/archive/2013/08/13/3254314.html
注意M(k-1)<N是一个很重要的条件

var n,m,ans,s:int64;
    p,k:longint;

function quick(x:int64; y:longint):int64;
  begin
    quick:=1;
    while y>0 do
    begin
      if y mod 2=1 then quick:=quick*x mod p;
      y:=y div 2;
      x:=x*x mod p;
    end;
  end;

begin
  readln(n,k,m,p);
  n:=n mod p;
  s:=quick(m mod p,k-2);
  ans:=n*s mod p*m mod p-(m+1)*m div 2 mod p*s mod p*int64(k-1) mod p;
  writeln((ans+p) mod p);
end.