M-SOLUTIONS プロコンオープン：E - Product of Arithmetic Progression
問題
解法
公差 d が 0 のとき，求める答えは x * x * ... * x となるので x^n．
そうでないときについて考える．まず，各項を d で割る．そうすると，t = x * mod_inverse(d) とおくと，
t, t + 1, t + 2, ... , t + n - 1
と初項が t で公差が 1 の等差数列を作ることができる．公差が 1 であるのでこれは連続した n 個の整数の積の形になっているので，
(t + n - 1)! / (t - 1)!
と言い換えることができる．前計算で階乗とその逆元を求めておくことで O(1) でこれを計算することができる．ここで，n が n >= 10^9 と大きく，n が大きいケースで TLE となってしまう．よく考えると，n >= mod (= 1000003) のとき，求める数列の要素には必ず mod の倍数が含まれている．よって，n >= mod のときは答えは 0 となり，n < mod のケースのみ先ほどの階乗を用いた計算を行えばよい．前計算がボトルネックとなり O(mod)．
解答
