eval"N,K,*A="+`dd`.split*?,
m,x,y=A.sum,1,0
A.reverse.map{y+=_1*x%m;x=x*K%m}
p y%m