#define MD 998244353
ll@N,@M,@Q;Mint m=M,B[N+1];B[1..N]=B[0..]*m+rd_ll()-1;rep(Q){ll@--l,@r;wt(B[r]-B[l]*m**(r-l)+1);}