GoodSubset | Topcoder Archive

Problem Statement

You have some cards, each containing a positive integer. You are given a int[] d. Each element of d is one of those integers. The integers are not necessarily distinct.

You are also given an int goodValue. You are interested in non-empty subsets of cards with the following property: The product of integers written on those cards is exactly equal to goodValue.

Let X be the number of subsets with the above property. Compute and return the value (X modulo 1,000,000,007).

Definition

Class:: GoodSubset
Method:: numberOfSubsets
Parameters:: int, int[]
Returns:: int
Method signature:: int numberOfSubsets(int goodValue, int[] d)
(be sure your method is public)

Constraints

goodValue will be between 1 and 2,000,000,000, inclusive.
d will contain between 1 and 100 elements, inclusive.
Each element of d will be between 1 and 2,000,000,000, inclusive.

Examples

```
10
```
```
{2,3,4,5}
```
```
Returns: 1
```
There is only one good subset:{2,5}.
```
6
```
```
{2,3,4,5,6}
```
```
Returns: 2
```
There are two good subsets: {2,3} and {6}.
```
1
```
```
{1,1,1}
```
```
Returns: 7
```
All non-empty subsets of this set of cards are good.

{1,2,3,4,5,6,7,8,9,10,11,12}

Returns: 6

```
5
```
```
{1,2,3,4}
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.