# Count Ways to Make Array With Product

## Intuition

1. Generate primes less than 10,000.
2. For each query, a. Decompose prime factors. b. Put the same primes into slots.

## Solution

``````
from typing import List
import math

class Solution:
def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
primes = self._get_primes(10000)
factorials = [1]
for i in range(1, 10001):
factorials.append((factorials[-1] * i) % 1000000007)

result = []
for slots, num in queries:
ways = 1
if slots > 1:
prime_factor_counts = self._prime_factor_counts(primes, num)
ways = 1
for counts in prime_factor_counts:
ways *= self._big_c(factorials, slots + num - 1, slots - 1)
result.append(ways % 1000000007)
return result

def _get_primes(self, m):
primes = set()
for i in range(2, m + 1):
is_prime = True
for p in primes:
if i % p == 0:
is_prime = False
break
if is_prime:
return primes

def _big_c(self, factorials, n, k):
return factorials[n] / factorials[k] / factorials[n - k]

def _prime_factor_counts(self, primes, num):
factors_count = {}
for p in primes:
if num % 2 == 0:
factors_count[p] = 0
while num % 2 == 0:
factors_count[p] += 1
num = num // p
if num == 1:
break
return factors_count.values()

``````