values of distinct integers, each greater than 1. Binary trees are built from them by these rules:
- every node holds a number from values, and the same number may be used any number of times;
- every node has either no children or exactly two, and in the latter case its number equals the product of its children's numbers.
Trees that differ only in which child is on the left and which is on the right count as different. How many such trees can be built? The answer can be large, so return it modulo 10^9 + 7.values=[3, 9, 27] → 8
Single-node trees: 3, 9, 27. Then 9 with children 3 and 3. For 27 = 3 · 9 the children can be (3, 9) or (9, 3), and in each case 9 can be a leaf or split into 3 and 3, giving 4 more trees. Total 3 + 1 + 4 = 8.
values=[6, 2, 7] → 3
6 = 2 · 3, but 3 is not in the set, so only the three single-node trees work.
values=[2, 4, 8] → 8
Single nodes: 3 trees. 4 = 2 · 2: 1 tree. 8 = 2 · 4 or 4 · 2, and the 4 may split further: 4 trees. Total 8.
values are distinctvalues=[3, 9, 27]
8
Run checks the first 3 tests in your browser. Submit checks all 101 tests on the server, hidden ones included.