<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>

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        # only unique integers in arr, all greater than 1, positive
        # arr size is up to 1000

        # output is the number of trees we can create
        # if the input is 1 -> 1
        # if it's 0 -> 0

        # single node trees are valid as well
        # we should probably set up valid children nodes

        # each node / value should have all the possible factors it can branch off to

        # since all the values are unique, we know that once we construct a tree and use that value, we can't use it again

        # for each number in the array (after we sort)
            # for this number, check if there are any factors, and we can use them infinitely, so squares work.
                # if there is a factor, create the two subtrees, binary = two children
        # prime numbers stop
        # 100 -> [10, 10], [2, 50]
        # 50 -> [10, 5]

        # recursion with memoization
        # set up a hashmap / memo lookup table
        lookup = {}
        array_set = set(arr)
        # set up a recursive function
        def recurse(value):
            # if the value is in our memo table, then we just return it
            if value in lookup:
                return lookup[value]
            # if the value has any more factors
            initial = 0
            for n in arr:
                if n > value:
                    break
                if value % n == 0:
                    if value // n in array_set:
                        if n * n == value: # [2, 4] are both in the array
                            initial += recurse(n) * recurse(n)
                        else:
                            initial += recurse(value // n) * recurse(n)
                    elif value == n: # value == n
                        initial += 1
            lookup[value] = initial
            return initial
                # we're going to iterate through the array and look for those
                # and we're going to call the recursive function, and multiply by two because we can swap the children
            # once we get all the values, we return
        arr.sort()
        result = 0
        for n in arr:
            result += recurse(n)
        print(lookup)
        return result % (10 ** 9 + 7)
        # once we finish recursion, we can sum across all the values in our lookup table to find the total number of trees

        # time complexity: O(N^2)
        # space complexity: O(N)
18100