atcoder.jp
xを有理数(つまり、整数とは限らない)として、x(x+1)(x+2)...とみなすと、剰余代数系ではある整数yが存在して y(y+1)(y+2)... を計算するのとおなじになる。これが最重要。
x(x+d)(x+2d)... = d^n * y(y +1) ... (y+n-1) (ただしy=x*d^(-1) mod 1e6+3)
ここでn が十分大きい場合この値は0になる。n < 1e6+3 かつ y < 1e6+3 のときだけ事前に計算しておくと、この計算はO(1)で可能になる。計算量はO(Q + 1e6)。
