#1735

Count Ways to Make Array With Product

candidate master · 1320 · lc hard +32 · verified · 54.5% accepted · 319 likes · top 47%

⚑ Combinatorics / Binomial Coefficients

Description

You are given queries[i] = [ni, ki]. For each query, count the number of ways to fill an array of size ni with positive integers whose product equals ki, modulo 109 + 7. Return the results as an array answer.

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]

Code

1
2
3