まず、公差$0$の等差数列の積は明らかに$x^n$です。これは、繰り返し二乗法を使って$O(\log N)$で求められます。
次に、公差$1$の等差数列の場合、$x, x + 1, \ldots, x + (n - 1)$のいずれかが$1,000,003$のとき、数列の積は$0$です。それ以外のとき、数列の積は$(x + (n - 1))! / (x - 1)!$です。これは、事前に$0$から$1,000,002$までの階乗を求めておくことで、$O(1)$で計算できます。
公差$2$以上の等差数列について考えます。$2$以上であるため、必ず逆数が存在します。ということで、数列の各要素を$d$で割ると、次のような数列になります。
\(\frac{x}{d}, \frac{x}{d} + 1, \frac{x}{d} + 2, \ldots, \frac{x}{d} + (n - 1)\)
見通しを良くするために$y = x / d$とおくと、次のようになります。
\(y, y + 1, y + 2, \ldots, y + (n - 1)\)
公差2以上の等差数列を、公差1の等差数列にすることができました。よってこの問題を解くことができました。
ソースコードはこちらです。mod用のクラスを事前に作っておくことで、modについて考える必要がなくなります。modの世界では、オーバーフローや浮動小数点数の誤差を心配することなく四則演算が行えるので便利です。
「数列の各要素を$d$で割って最後に$d^n$をかける」という操作を行うことで、解ける問題になりました。面白いです。コンテスト中は、未知のアルゴリズムを使うのかなと考えていたのですが、全然違いました…（笑）まだまだ問題の言い換え力が足りないことを実感したので、これからも問題を解き続け、少しずつ言い換えのバリエーションを増やしていこうと思います。