まず、この問題の条件は次のようなものに言い換えられます。

  • MM 以下の素数を p1,p2,,pKp_{1},p_{2},\cdots ,p_{K} とする。また、「MM 以下の最大の pip_i の整数乗」を pimip_{i}^{m_{i}} とする。
  • それぞれの要素を p1n1×p2n2×pKnKp_{1}^{n_{1}}\times p_{2}^{n_{2}} \times \cdots p_{K}^{n_{K}} と素因数分解する。 11 以上 KK 以下の全ての ii に対し、全ての要素に対する nin_{i} の最大値が mim_{i} と等しい。

ここで、 ni=min_{i}=m_{i} とならないような整数についてはその ii に対する条件に関係しません。

また、 11 以上 MM 以下の全ての整数について、 ni=min_{i}=m_{i} となるような ii は最大でも 11 つしか存在しないことが、次の事実が成り立つことから証明できます。

  • 全ての ii について、M<pimi\sqrt{M} < p_{i}^{m_{i}} が成り立つ。

これは、次のように証明できます。

  • M<pi\sqrt{M} < p_{i} である場合、mi=1m_{i}=1 である。そのため、この ii について成り立つ。
  • piMp_{i} \leq \sqrt{M} である場合、もしある M\sqrt{M} 以下の整数 xx が存在し pimi=xp_{i}^{m_{i}}=x である場合、 x×pix \times p_{i}MM 以下であり、かつより大きい mim_{i} が取れるため、矛盾する。そのため、この ii について成り立つ。

そのため、次のようなDPを考えることができます。

  • DP[i][j]=piDP[i][j] = p_{i} までに対し pimip_{i}^{m_{i}} の倍数であるような数列の要素を選び終わり、残りの要素の個数が jj であるような選び方の個数。

ただし、DP[K][j]DP[K][j] まで遷移しきった後、最後に答えを求めるための計算が必要なことに注意してください。

これは次のような初期値および遷移になります。

  • DP[0][N]=1DP[0][N]=1
  • DP[i+1][jk]+=DP[i][j]×(jk)×floor(M/(pimi))kDP[i+1][j-k]+=DP[i][j] \times \binom{j}{k} \times {\rm floor}(M/(p_{i}^{m_{i}}))^{k} ただし、 k>0k>0

ここで、 DP[0][N]DP[0][N] の初期値を N!N! にし、 (jk)\binom{j}{k}(k!)1(k!)^{-1} で置き換えることを考えます。このようにすることで、全ての jj に対し同じ遷移をすることができ、NTTで遷移を高速化することができるようになります。そのため、答えを O(π(M)NlogN)Ο(\pi(M) N \log N) で求めることができます。

ここで、制約が N2000N\leq 2000 であるため、 20012001 番目の素数である 1739317393 以上の MM に対しては常に答えが 00 になります。これに対し場合分けを行うことで、制約の範囲内で答えを時間内に求めることができます。