<p>You are given two integers <code>n</code> and <code>maxValue</code>, which are used to describe an <strong>ideal</strong> array.</p>

<p>A <strong>0-indexed</strong> integer array <code>arr</code> of length <code>n</code> is considered <strong>ideal</strong> if the following conditions hold:</p>

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

<p>Return <em>the number of <strong>distinct</strong> ideal arrays of length </em><code>n</code>. Since the answer may be very large, return it modulo <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2, maxValue = 5
<strong>Output:</strong> 10
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 5, maxValue = 3
<strong>Output:</strong> 11
<strong>Explanation:</strong> 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 2<sup>nd</sup> 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 2<sup>nd</sup> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= maxValue &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
    def idealArrays(self, n: int, maxValue: int) -> int:
        def extended_euclidean(a, b):
            if not b:
                #return (C, D)
                return (1, 0) #1 * a + 0 * b = gcd

            last_C, last_D = extended_euclidean(b, a % b)
            return last_D, last_C - last_D * (a // b)


        def sieve_of_eratosthenes(n):
            primes = [True] * (n - 1)
            primes_list = []

            for i in range(2, n + 1):
                if primes[i - 2]:
                    primes_list.append(i)
                    for x in range(i ** 2, n + 1, i):
                        primes[x - 2] = False

            return primes_list

        def get_prime_cnts(num):
            cnts = {}

            for p in primes:
                while not num % p:
                    cnts[p] = cnts.get(p, 0) + 1
                    num //= p

            return list(cnts.values())



        primes = sieve_of_eratosthenes(maxValue)
        factorials = [1]
        reciprocals = [1]
        res = 0
        mod = 10 ** 9 + 7

        for i in range(n + 20):
            factorials.append(factorials[-1] * (i + 1) % mod)
            reciprocals.append(extended_euclidean(mod, factorials[-1])[1])

        for val in range(1, maxValue + 1):
            cnts = get_prime_cnts(val)
            current_cnt = 1

            for cnt in cnts:
                current_cnt *= factorials[n + cnt - 1] * reciprocals[cnt] * reciprocals[n - 1]
                current_cnt %= mod

            res += current_cnt
            res %= mod

        return res
17800