Given an array of unique integers, each integer is strictly greater than 1.
We make a binary tree using these integers and each number may be used for any number of times.
Each non-leaf node's value should be equal to the product of the values of it's children.
How many binary trees can we make?  Return the answer modulo 10 ** 9 + 7.
Example 1:
Input: A = [2, 4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]
Example 2:
Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
Note:
1 <= A.length <= 1000.
2 <= A[i] <= 10 ^ 9.
class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        
        mod = 10**9 + 7

        nums_set = set(A)
        nums = A.copy()
        nums.sort()
        counts = {}
        total = 0

        for n in nums:
            n_count = 1
            for d in nums:
                if d * d > n:
                    break
                if n % d != 0:
                    continue
                e = n // d
                if e not in nums_set:
                    continue

                subtrees = (counts[d] * counts[e]) % mod
                if d != e:
                    subtrees = (subtrees * 2) % mod
                n_count = (n_count + subtrees) % mod
            counts[n] = n_count % mod
            total = (total + n_count) % mod

        return total

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        
        mod = 10**9 + 7

        nums_set = set(A)
        nums = A.copy()
        nums.sort()
        counts = {}
        total = 0

        for n in nums:
            n_count = 1
            for d in nums:
                if d * d > n:
                    break
                if n % d != 0:
                    continue
                e = n // d
                if e not in nums_set:
                    continue

                subtrees = (counts[d] * counts[e]) % mod
                if d != e:
                    subtrees = (subtrees * 2) % mod
                n_count = (n_count + subtrees) % mod
            counts[n] = n_count % mod
            total = (total + n_count) % mod

        return total
