# Count Ways to Make Array With Product
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-ways-to-make-array-with-product)
Canonical: https://scaleengineer.com/dsa/problems/count-ways-to-make-array-with-product
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
---
## Problem
You are given a 2D integer array, `queries`. For each `queries[i]`, where `queries[i] = [ni, ki]`, find the number of different ways you can place positive integers into an array of size `ni` such that the product of the integers is `ki`. As the number of ways may be too large, the answer to the `ith` query is the number of ways **modulo** `109 + 7`.

Return _an integer array_ `answer` _where_ `answer.length == queries.length`_, and_ `answer[i]` _is the answer to the_ `ith` _query._

**Example 1:**

**Input:** queries = [[2,6],[5,1],[73,660]]
**Output:** [4,1,50734910]
**Explanation:** Each query is independent.
[2,6]: There are 4 ways to fill an array of size 2 that multiply to 6: [1,6], [2,3], [3,2], [6,1].
[5,1]: There is 1 way to fill an array of size 5 that multiply to 1: [1,1,1,1,1].
[73,660]: There are 1050734917 ways to fill an array of size 73 that multiply to 660. 1050734917 modulo 109 + 7 = 50734910.

**Example 2:**

**Input:** queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
**Output:** [1,2,3,10,5]

**Constraints:**

* `1 <= queries.length <= 104 `
* `1 <= ni, ki <= 104`

# Approaches
## Per-Query Factorization
This approach tackles the problem by first understanding its mathematical structure. The problem of finding the number of arrays of size `n` with a product `k` can be broken down by considering the prime factorization of `k`. If `k = p_1^{e_1} * p_2^{e_2} * ... * p_m^{e_m}`, then for each prime factor `p_i`, we need to distribute its total power `e_i` among the `n` elements of the array. This is a classic combinatorial problem known as "stars and bars". The number of ways to distribute `e` identical items into `n` distinct bins is `C(n + e - 1, e)`. The total number of ways is the product of these values for each prime factor. This approach calculates this for each query individually.
**Time:** `O(P + Q * sqrt(max_k))`, where `P` is the precomputation time for factorials, `O(max_n + max_e)`. With `Q <= 10^4` and `max_k <= 10^4`, the total time is dominated by processing queries, resulting in `O(10^4 * sqrt(10^4)) = O(10^6)` operations, which is acceptable. · **Space:** `O(max_n + max_e)` to store the precomputed factorial and inverse factorial arrays. Given the constraints, this is `O(10^4)`.
**Pros:** Conceptually straightforward, directly translating the mathematical formula.; Implementation is relatively simple.
**Cons:** The prime factorization step `O(sqrt(k))` is performed for every query, which can be inefficient if the number of queries is large.
### Explanation
The core of the solution is to transform the multiplicative problem into a set of independent additive problems.
Let the array be `A = [a_1, a_2, ..., a_n]` and `Product(A) = k`.
Let the prime factorization of `k` be `p_1^{e_1} * p_2^{e_2} * ... * p_m^{e_m}`.
Each element `a_i` can be written as `a_i = p_1^{e_{i1}} * p_2^{e_{i2}} * ... * p_m^{e_{im}}`.
The condition `Product(A) = k` implies that for each prime `p_j`, the sum of its exponents across all `a_i` must equal `e_j`. That is, `sum_{i=1 to n} e_{ij} = e_j`.
This is a "stars and bars" problem. The number of non-negative integer solutions to this equation is `C(n + e_j - 1, e_j)`.
Since the distribution of exponents for each prime is independent, the total number of ways is the product: `ways = Product_{j=1 to m} C(n + e_j - 1, e_j)`.
For each query `[n, k]`, we perform the following steps:
1. Find the prime factors of `k` and their exponents using trial division (iterating from 2 up to `sqrt(k)`).
2. For each exponent `e`, calculate `C(n + e - 1, e)` modulo `10^9 + 7`.
3. Multiply all these results together to get the final answer for the query.
To compute `C(N, R) % MOD` efficiently, we precompute factorials and their modular multiplicative inverses. This is done once before processing any queries.
```java
class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MAX_N_PLUS_E = 10000 + 14; // max_n=10000, max_e for k=10000 is for 2^13=8192, so e=13.
    private static long[] fact = new long[MAX_N_PLUS_E];
    private static long[] invFact = new long[MAX_N_PLUS_E];

    static {
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i < MAX_N_PLUS_E; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
            invFact[i] = power(fact[i], MOD - 2);
        }
    }

    private static long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    private long nCr_mod_p(int n, int r) {
        if (r < 0 || r > n) return 0;
        if (r > n / 2) r = n - r;
        return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
    }

    public int[] waysToFillArray(int[][] queries) {
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int n = queries[i][0];
            int k = queries[i][1];
            
            long currentWays = 1;
            
            for (int p = 2; p * p <= k; p++) {
                if (k % p == 0) {
                    int count = 0;
                    while (k % p == 0) {
                        count++;
                        k /= p;
                    }
                    currentWays = (currentWays * nCr_mod_p(n + count - 1, count)) % MOD;
                }
            }
            if (k > 1) {
                int count = 1;
                currentWays = (currentWays * nCr_mod_p(n + count - 1, count)) % MOD;
            }
            ans[i] = (int) currentWays;
        }
        return ans;
    }
}
```
### Algorithm
- 1. Precompute factorials and their modular inverses up to a maximum possible value of `n + e - 1`. Given `n <= 10^4` and `k <= 10^4`, the maximum exponent `e` is for `2^e <= 10^4`, which is `e=13`. So we need factorials up to `10000 + 13 = 10013`.
- 2. Create a result array `answer` of the same size as `queries`.
- 3. Iterate through each query `[n, k]` in `queries`.
- 4. For each query, initialize a variable `ways = 1`.
- 5. Find the prime factorization of `k`. Iterate a divisor `d` from 2 up to `sqrt(k)`.
- 6. If `d` divides `k`, count its exponent `e`. Then, calculate `C(n + e - 1, e)` using the precomputed tables and multiply it into `ways`. Update `k` by dividing out `d^e`.
- 7. If `k` is still greater than 1 after the loop, it is a prime factor itself. Its exponent is 1. Calculate `C(n + 1 - 1, 1) = C(n, 1) = n` and multiply it into `ways`.
- 8. Store the final `ways` in the `answer` array.
- 9. Return `answer`.

## Optimized Approach with Sieve Precomputation
This approach enhances the previous method by optimizing the most time-consuming part: prime factorization. Instead of re-calculating prime factors for `k` in each query, we can pre-process all numbers up to `max_k` to find their prime factors quickly. A sieve method is perfect for this. We can build a Smallest Prime Factor (SPF) array for all numbers up to `10^4`. Using this SPF array, the prime factorization of any number `k` can be done in `O(log k)` time. This significantly speeds up the processing of each query.
**Time:** `O(max_k * log(log(max_k)) + max_n + Q * log(max_k))`. The precomputation is dominated by the sieve. Each query takes `O(log k)` time. This is very efficient for the given constraints. · **Space:** `O(max_k + max_n)` for the `spf` array and the factorial arrays. Given the constraints, this is `O(10^4)`.
**Pros:** Highly efficient due to fast prime factorization.; Optimal solution for the given constraints.
**Cons:** More complex to implement due to the sieve.; Uses more memory for the `spf` array.
### Explanation
The mathematical foundation remains the same as the first approach: using stars and bars on the exponents of prime factors. The improvement lies in the execution.
**Precomputation Phase:**
1. **Sieve for SPF:** We create an array `spf` of size `max_k + 1`. `spf[i]` will store the smallest prime factor of `i`. We can populate this array using a method similar to the Sieve of Eratosthenes in `O(max_k * log(log(max_k)))` time.
2. **Factorials:** We precompute factorials and their modular inverses up to `max_n + max_e - 1`, just like in the previous approach. This takes `O(max_n + max_e)`.
**Query Processing Phase:**
1. For each query `[n, k]`, we find its prime factorization.
2. Instead of trial division, we repeatedly divide `k` by `spf[k]` until `k` becomes 1. This gives us all prime factors and their counts in `O(log k)` time.
3. For each prime factor `p` with exponent `e`, we calculate `C(n + e - 1, e)` and multiply the results modulo `10^9 + 7`.
This precomputation of SPF allows each query to be answered much faster, making the overall solution highly efficient for a large number of queries.
```java
class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MAX_K = 10001;
    private static final int MAX_N_PLUS_E = 10000 + 14;
    
    private static int[] spf = new int[MAX_K];
    private static long[] fact = new long[MAX_N_PLUS_E];
    private static long[] invFact = new long[MAX_N_PLUS_E];

    static {
        for (int i = 1; i < MAX_K; i++) spf[i] = i;
        for (int i = 2; i * i < MAX_K; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j < MAX_K; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }

        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i < MAX_N_PLUS_E; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
            invFact[i] = power(fact[i], MOD - 2);
        }
    }

    private static long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    private long nCr_mod_p(int n, int r) {
        if (r < 0 || r > n) return 0;
        if (r > n / 2) r = n - r;
        return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
    }

    public int[] waysToFillArray(int[][] queries) {
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int n = queries[i][0];
            int k = queries[i][1];
            
            long currentWays = 1;
            
            while (k > 1) {
                int p = spf[k];
                int count = 0;
                while (k > 0 && k % p == 0) {
                    count++;
                    k /= p;
                }
                currentWays = (currentWays * nCr_mod_p(n + count - 1, count)) % MOD;
            }
            ans[i] = (int) currentWays;
        }
        return ans;
    }
}
```
### Algorithm
- 1. **Sieve:** Create an array `spf` up to `max_k`. Initialize `spf[i] = i`. Iterate from `i = 2` to `sqrt(max_k)`. If `spf[i] == i` (i.e., `i` is prime), iterate through its multiples `j = i*i, i*i+i, ...` and set `spf[j] = i` if `spf[j]` hasn't been set yet.
- 2. **Factorials:** Precompute factorials and their modular inverses up to `max_n + max_e - 1`.
- 3. Iterate through each query `[n, k]`.
- 4. For each query, initialize `ways = 1`.
- 5. While `k > 1`:
    a. Get the smallest prime factor `p = spf[k]`.
    b. Count how many times `p` divides `k`. Let this be `e`.
    c. Update `k` by dividing out `p^e`.
    d. Calculate `C(n + e - 1, e)` and multiply it into `ways`.
- 6. Store the final `ways` in the `answer` array.
- 7. Return `answer`.

# Solutions
### Java

```java
class Solution {
private
  static final int N = 10020;
private
  static final int MOD = (int)1 e9 + 7;
private
  static final long[] F = new long[N];
private
  static final long[] G = new long[N];
private
  static final List<Integer>[] P = new List[N];
  static {
    F[0] = 1;
    G[0] = 1;
    Arrays.setAll(P, k->new ArrayList<>());
    for (int i = 1; i < N; ++i) {
      F[i] = F[i - 1] * i % MOD;
      G[i] = qmi(F[i], MOD - 2, MOD);
      int x = i;
      for (int j = 2; j <= x / j; ++j) {
        if (x % j == 0) {
          int cnt = 0;
          while (x % j == 0) {
            ++cnt;
            x /= j;
          }
          P[i].add(cnt);
        }
      }
      if (x > 1) {
        P[i].add(1);
      }
    }
  }
public
  static long qmi(long a, long k, long p) {
    long res = 1;
    while (k != 0) {
      if ((k & 1) == 1) {
        res = res * a % p;
      }
      k >>= 1;
      a = a * a % p;
    }
    return res;
  }
public
  static long comb(int n, int k) {
    return (F[n] * G[k] % MOD) * G[n - k] % MOD;
  }
public
  int[] waysToFillArray(int[][] queries) {
    int m = queries.length;
    int[] ans = new int[m];
    for (int i = 0; i < m; ++i) {
      int n = queries[i][0], k = queries[i][1];
      long t = 1;
      for (int x : P[k]) {
        t = t * comb(x + n - 1, n - 1) % MOD;
      }
      ans[i] = (int)t;
    }
    return ans;
  }
}

```

### CPP

```cpp
int N = 10020 ; int MOD = 1e9 + 7 ; long f [ 10020 ]; long g [ 10020 ]; vector < int > p [ 10020 ]; long qmi ( long a , long k , long p ) { long res = 1 ; while ( k != 0 ) { if (( k & 1 ) == 1 ) { res = res * a % p ; } k >>= 1 ; a = a * a % p ; } return res ; } int init = []() { f [ 0 ] = 1 ; g [ 0 ] = 1 ; for ( int i = 1 ; i < N ; ++ i ) { f [ i ] = f [ i - 1 ] * i % MOD ; g [ i ] = qmi ( f [ i ], MOD - 2 , MOD ); int x = i ; for ( int j = 2 ; j <= x / j ; ++ j ) { if ( x % j == 0 ) { int cnt = 0 ; while ( x % j == 0 ) { ++ cnt ; x /= j ; } p [ i ]. push_back ( cnt ); } } if ( x > 1 ) { p [ i ]. push_back ( 1 ); } } return 0 ; }(); int comb ( int n , int k ) { return ( f [ n ] * g [ k ] % MOD ) * g [ n - k ] % MOD ; } class Solution { public: vector < int > waysToFillArray ( vector < vector < int >>& queries ) { vector < int > ans ; for ( auto & q : queries ) { int n = q [ 0 ], k = q [ 1 ]; long long t = 1 ; for ( int x : p [ k ]) { t = t * comb ( x + n - 1 , n - 1 ) % MOD ; } ans . push_back ( t ); } return ans ; } };
```

### Python

```python
N = 10020 MOD = 10 ** 9 + 7 f = [ 1 ] * N g = [ 1 ] * N p = defaultdict ( list ) for i in range ( 1 , N ): f [ i ] = f [ i - 1 ] * i % MOD g [ i ] = pow ( f [ i ], MOD - 2 , MOD ) x = i j = 2 while j <= x // j : if x % j == 0 : cnt = 0 while x % j == 0 : cnt += 1 x //= j p [ i ]. append ( cnt ) j += 1 if x > 1 : p [ i ]. append ( 1 ) def comb ( n , k ): return f [ n ] * g [ k ] * g [ n - k ] % MOD class Solution : def waysToFillArray ( self , queries : List [ List [ int ]]) -> List [ int ]: ans = [] for n , k in queries : t = 1 for x in p [ k ]: t = t * comb ( x + n - 1 , n - 1 ) % MOD ans . append ( t ) return ans
```