それぞれのパラメータが最終的な答えにどの程度寄与するかを考えます。

あるパラメータ i(1iN)i (1 \leq i \leq N) から、1つのパラメータの値 p(1pPi)p (1 \leq p \leq P_i) を選ぶ回数は、ii 番目以外のパラメータを選ぶ場合の数と等しいです。

上記の場合の数は、全てのパラメータの選び方をi番目のパラメータの選び方で割った値になります。これは、

j=1NPjPi\frac{\prod_{j = 1}^{N} P_j}{P_i}

で求めることができます。 割り算を行うにあたって、mod 109+7mod\ 10^9+7 の空間で PiP_i の逆元を求める modinvmodinv などの関数を用意する必要があります。

パラメータの値1つ1つに対してこのまま計算を行おうとすると、パラメータiiに対して PiP_i 回の計算が必要になり、制限時間内に回答することができません。 しかし、1つのパラメータのみに着目すると、パラメータの値をどのように取ってもかける場合の数は等しくなるため、等差数列の和の公式を用いることでまとめて計算を行うことができます。

modの逆元を計算する部分に O(logmax(Pi))O(\log{max({P_i}})) かかるため、最終的な計算量は O(Nlogmax(Pi))O(N\log{max({P_i}})) となります。

PP に対して左右から累積積を計算しておくと、各 ii に対して ii 番目以外のパラメータを選ぶ場合の数を O(1)O(1) で求めることができ、全体として O(N)O(N) で回答することもできます。