$(a^k-a^0)(a^k-a^1)(a^k-a^2)\cdots(a^k-a^{k-1})$

要求：

• 可以进行不超过 $O(k \log k)$ 的预处理
• 随机查询任意 $k \le 500000$，单次查询 $O(\log k)$ 以下。