You are given two integers n and maxValue, which are used to describe an ideal array.

A 0-indexed integer array arr of length n is considered ideal if the following conditions hold:


	Every arr[i] is a value from 1 to maxValue, for 0 &lt;= i &lt; n.
	Every arr[i] is divisible by arr[i - 1], for 0 &lt; i &lt; n.


Return the number of distinct ideal arrays of length n. Since the answer may be very large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: n = 2, maxValue = 5
Output: 10
Explanation: The following are the possible ideal arrays:
- Arrays starting with the value 1 (5 arrays): [1,1], [1,2], [1,3], [1,4], [1,5]
- Arrays starting with the value 2 (2 arrays): [2,2], [2,4]
- Arrays starting with the value 3 (1 array): [3,3]
- Arrays starting with the value 4 (1 array): [4,4]
- Arrays starting with the value 5 (1 array): [5,5]
There are a total of 5 + 2 + 1 + 1 + 1 = 10 distinct ideal arrays.


Example 2:

Input: n = 5, maxValue = 3
Output: 11
Explanation: The following are the possible ideal arrays:
- Arrays starting with the value 1 (9 arrays): 
   - With no other distinct values (1 array): [1,1,1,1,1] 
   - With 2nd distinct value 2 (4 arrays): [1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
   - With 2nd distinct value 3 (4 arrays): [1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
- Arrays starting with the value 2 (1 array): [2,2,2,2,2]
- Arrays starting with the value 3 (1 array): [3,3,3,3,3]
There are a total of 9 + 1 + 1 = 11 distinct ideal arrays.


&nbsp;
Constraints:


	2 &lt;= n &lt;= 104
	1 &lt;= maxValue &lt;= 104


from math import sqrt

class Solution:
    def primesUpTo(self, n):
        primes = set(range(2, n + 1))
        for i in range(2, n):
            if i in primes:
                it = i * 2
                while it <= n:
                    if it in primes:
                        primes.remove(it)
                    it += i

        return primes

    def getPrimeFactors(self, n, primes):
        ret = {}
        sq = int(math.sqrt(n))

        for p in primes:
            if n in primes:
                ret[n] = 1
                break

            while n % p == 0:
                ret[p] = ret.get(p, 0) + 1
                n //= p

            if n <= 1:
                break

        return ret
        
    def idealArrays(self, n: int, maxValue: int) -> int:
        mod = 10**9 + 7
        ret = 0
        primes = self.primesUpTo(maxValue)
        
        for num in range(1, maxValue + 1):
            # find number of arrays that can end with num
            # for each prime factor, we can add it at any index i that we want
            pf = self.getPrimeFactors(num, primes)
            cur = 1
            for d in pf:
                ct = pf[d]
                v = n
                # there are (n + 1) choose k ways to add k prime factors
                for add in range(1, ct):
                    v *= (n + add)
                    v //= (add + 1)
                
                cur = (cur * v) % mod
                    
            ret = (ret + cur) % mod
                    
        return ret
class Solution {
    int M =(int)1e9+7;
    public int idealArrays(int n, int maxValue) {
        long ans = 0;
        int N = n+maxValue;
        long[] inv = new long[N];
        long[] fact = new long[N];
        long[] factinv = new long[N];
        inv[1]=fact[0]=fact[1]=factinv[0]=factinv[1]=1;
        for (int i = 2; i < N; i++){ // mod inverse
            inv[i]=M-M/i*inv[M%i]%M;
            fact[i]=fact[i-1]*i%M;
            factinv[i]=factinv[i-1]*inv[i]%M;
        }
        for (int i = 1; i <= maxValue; i++){
            int tmp = i;
            Map<Integer, Integer> map = new HashMap<>();
            for (int j = 2; j*j<= tmp; j++){
                while(tmp%j==0){  // prime factorization.
                    tmp/=j;
                    map.merge(j, 1, Integer::sum);
                }
            }
            if (tmp>1){
                map.merge(tmp, 1, Integer::sum);
            }
            long gain=1;
            for (int val : map.values()){ // arranges all the primes.
                gain *= comb(n+val-1, val, fact, factinv);
                gain %= M;
            }
            ans += gain;
            ans %= M;
        }

        return (int)ans;
    }

    private long comb(int a, int b, long[] fact, long[] factinv){
        return fact[a]*factinv[b]%M*factinv[a-b]%M;
    }
}
int comb[10001][14] = { 1 }, cnt[10001][14] = {}, mod = 1000000007;
class Solution {
public: 
int idealArrays(int n, int maxValue) {
    if (comb[1][1] == 0) { // one-time computation.
        for (int s = 1; s <= 10000; ++s) // nCr (comb)
            for (int r = 0; r < 14; ++r)
                comb[s][r] = r == 0 ? 1 : (comb[s - 1][r - 1] + comb[s - 1][r]) % mod;
        for (int div = 1; div <= 10000; ++div) { // Sieve of Eratosthenes
            ++cnt[div][0];
            for (int i = 2 * div; i <= 10000; i += div)
                for (int bars = 0; cnt[div][bars]; ++bars)
                    cnt[i][bars + 1] += cnt[div][bars];
        }
    }
    int res = 0;
    for (int i = 1; i <= maxValue; ++i)
        for (int bars = 0; bars < min(14, n) && cnt[i][bars]; ++bars)
            res = (1LL * cnt[i][bars] * comb[n - 1][bars] + res) % mod;
    return res;
}
};
/**
 * @param {number} n
 * @param {number} maxValue
 * @return {number}
 */
var idealArrays = function(n, maxValue) {
  const mod = 1e9 + 7;
  let cur = 0;
  let arr = Array(2).fill().map(() => Array(maxValue).fill(1));
  for (let l = 2; l <= n; l++) {
    const prev = arr[cur];
    const next = arr[1-cur];
    for (let s = 1; s <= maxValue; s++) {
      let res = 0;
      for (let m = 1; m * s <= maxValue; m++) {
        res = (res + prev[m * s - 1]) % mod;
      }
      next[s-1] = res;
    }
    cur = 1 - cur;
  }
  const res = arr[cur].reduce((a, b) => (a + b) % mod, 0);
  return res;
};
Count the Number of Ideal Arrays