<p>Given an array of unique integers, <code>arr</code>, where each integer <code>arr[i]</code> is strictly greater than <code>1</code>.</p>

<p>We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node&#39;s value should be equal to the product of the values of its children.</p>

<p>Return <em>the number of binary trees we can make</em>. The answer may be too large so return the answer <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [2,4]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can make these trees: <code>[2], [4], [4, 2, 2]</code></pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [2,4,5,10]
<strong>Output:</strong> 7
<strong>Explanation:</strong> We can make these trees: <code>[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]</code>.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 1000</code></li>
	<li><code>2 &lt;= arr[i] &lt;= 10<sup>9</sup></code></li>
	<li>All the values of <code>arr</code> are <strong>unique</strong>.</li>
</ul>

from collections import defaultdict

class Solution:
    M = 10 ** 9 + 7

    def build_child_list(self, arr):
        _set = set(arr)
        n = len(arr)
        res = defaultdict(list)
        for i in range(n):
            for j in range(i):
                rem = arr[i] % arr[j]
                if rem:
                    continue
                num = arr[i] // arr[j]
                if num in _set and arr[j] <= num:
                    res[arr[i]].append((arr[j], num))
        return res

    def compute_tree_count(self, arr, child_list):
        res = defaultdict(int)
        for num in arr:
            res[num] = 1
            if num not in child_list:
                continue
            for left, right in child_list[num]:
                res[num] += ((1 + (left < right)) * res[left] * res[right]) % self.M
        return res

    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        arr = sorted(arr)
        child_list = self.build_child_list(arr)
        tree_count = self.compute_tree_count(arr, child_list)
        res = 0
        for cnt in tree_count.values():
            res = (res + cnt) % self.M
        return res
        
17100