求める値が素数 \(p\) について何回割り切れるか求めます。これは、各 \(p^n \, (n > 0)\) についてスコアが \(p^n\) の倍数であるような \(P\) の総数を足し合わせて得られます。フェルマーの小定理より、\(10^9 + 6\) で割った余りを求めればよいです。

スコアが \(p^n\) の倍数であることは、ある \(1 \leq i \leq \frac{N}{K}\) が存在して、\(B_{(i - 1)K + 1}, B_{(i - 1)K + 2} \dots, B_{iK}\) が全て \(a\) の倍数であることと同値です。よって、\(A\) の要素のうち \(p^n\) の倍数であるものの個数を \(m\) とおくと、以下の問題を解けばよいことになります。

\(0\) が書かれたボール \(N-m\) 個と \(1\) が書かれたボール \(m\) 個を一列に並べる方法であって、以下の条件を満たすものは何通りあるか求めよ。ただし、同じ整数が書かれたボールも区別する。

• ある \(1 \leq i \leq \frac{N}{K}\) が存在して、左から\((i - 1)K + 1\) 番目 \(, \dots, \) \(iK\) 番目のボールに書かれた整数が全て \(1\) である。

包除原理を用いると、これは \(\displaystyle m!(N - m)! \sum_{i = 1}^{\left\lfloor \frac{m}{K} \right\rfloor} (-1)^{i - 1} \binom{\frac{N}{K}} {i} \binom{N - iK}{m - iK} \) と計算できます。全ての \(p^n\) について \(m\) を足し合わせた値は \(O(N \log (\max A))\) 程度であるので、計算回数の総和は \(O\left(\frac{N \log (\max A)}{K}\right)\) になります。

\(10^9 + 6 = 2 \times 500000003\) と素因数分解されることを利用すると、\(500000003\) で割った余りおよび偶奇の情報から階乗や二項係数を \(10^9 + 6\) で割った余りを求めることができます。