それぞれのパラメータが最終的な答えにどの程度寄与するかを考えます。
あるパラメータ から、1つのパラメータの値 を選ぶ回数は、 番目以外のパラメータを選ぶ場合の数と等しいです。
上記の場合の数は、全てのパラメータの選び方をi番目のパラメータの選び方で割った値になります。これは、
で求めることができます。 割り算を行うにあたって、 の空間で の逆元を求める などの関数を用意する必要があります。
パラメータの値1つ1つに対してこのまま計算を行おうとすると、パラメータに対して 回の計算が必要になり、制限時間内に回答することができません。 しかし、1つのパラメータのみに着目すると、パラメータの値をどのように取ってもかける場合の数は等しくなるため、等差数列の和の公式を用いることでまとめて計算を行うことができます。
modの逆元を計算する部分に かかるため、最終的な計算量は となります。
に対して左右から累積積を計算しておくと、各 に対して 番目以外のパラメータを選ぶ場合の数を で求めることができ、全体として で回答することもできます。