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.

Difficulty: interview

Starter code:

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        

Solutions:
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:
        factorSet = set(A)
        A.sort()
        treeCount = collections.defaultdict(lambda : 1)
        
        n = len(A)
        end = 0
        for num in A:
            sqrt = int(math.sqrt(num)+1)
            while end < n and A[end] <= sqrt:
                end += 1
            count = 0
            for _, p in zip(list(range(end)), A):
                if num % p == 0 and (q := num // p) in factorSet and p <= q:
                    count += 2*treeCount[p]*treeCount[q] if p != q else treeCount[p]*treeCount[q]
            treeCount[num] += count
        return sum(treeCount.values()) % (1000_000_000 + 7)
        


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        factorSet = set(A)
        A.sort()
        treeCount = {}

        for num in A:
            count = 1
            for p, pCount in list(treeCount.items()):
                q, rem = divmod(num, p)
                if p > q:
                    break
                if rem == 0:
                    tmp = pCount * treeCount.get(q, 0)
                    count += tmp if p == q else 2*tmp
            treeCount[num] = count
        return sum(treeCount.values()) % (1000_000_000 + 7)


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        dp = {}
        res = 0
        for i in range(len(A)):
            dp[A[i]] = 1
            for j in range(i):
                if A[j] * A[j] == A[i]:
                    dp[A[i]] += dp[A[j]] * dp[A[j]]
                    dp[A[i]] %= 1000_000_007
                elif A[j] * A[j] > A[i] and A[i] % A[j] == 0:
                    dp[A[i]] += dp[A[j]] * dp.get(A[i] // A[j], 0) * 2
                    dp[A[i]] %= 1000_000_007
        res = sum([v for _, v in dp.items()])
        res %= 1000_000_007
        return res

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        dp = {}
        res = 0
        for i in range(len(A)):
            dp[A[i]] = 1
            for j in range(i):
                if A[j] * A[j] == A[i]:
                    dp[A[i]] += dp[A[j]] * dp[A[j]]
                    dp[A[i]] %= 1000_000_007
                elif A[j] * A[j] > A[i]:
                    div = A[i] // A[j]
                    if div * A[j] == A[i] and div in dp:
                        dp[A[i]] += dp[A[j]] * dp[div] * 2
                        dp[A[i]] %= 1000_000_007
            res += dp[A[i]]
            res %= 1000_000_007
        return res

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        dp = {}
        res = 0
        for i in range(len(A)):
            dp[A[i]] = 1
            for j in range(i):
                if A[j] * A[j] == A[i]:
                    dp[A[i]] += dp[A[j]] * dp[A[j]]
                    dp[A[i]] %= 1000_000_007
                elif A[j] * A[j] > A[i] and A[i] % A[j] == 0:
                    dp[A[i]] += dp[A[j]] * dp.get(A[i] // A[j], 0) * 2
                    dp[A[i]] %= 1000_000_007
            res += dp[A[i]]
            res %= 1000_000_007
        return res

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        cache = dict()
        iSet = set(A)
        def helper(i):
            if i not in cache:
                count = 1
                for j in range(len(A)):
                    if i != A[j] and i % A[j] == 0:
                        if i//A[j] in iSet:
                            count += helper(A[j]) * helper(i//A[j])
                cache[i] = count
            return cache[i]
        ans = 0
        for i in range(len(A)):
            ans += helper(A[i])
        return ans % 1000000007


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A=sorted(A)
        res=dict()
        for idx, a in enumerate(A):
            if idx==0:
                res[a]=1
            else:
                res[a]=1
                for j in range(idx):
                    if (a%A[j]==0) and (a//A[j] in A):
                        res[a]+=res[A[j]]*res[a//A[j]]
        return sum(res.values())%(10**9+7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        
        A.sort()
        
        dp = [1 for _ in range(len(A))]
        
        for i in range(len(A)):
            
            for j in range(i):
                
                time, remain = divmod(A[i], A[j])

                if remain == 0 and time in A:

                    dp[i] += (dp[j] * dp[A.index(time)])
                        
        return sum(dp) % (10**9 + 7)
            
            


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        d = {}
        Aset = set(A)
        A.sort()
        ans = 0
        for i in range(len(A)):
            d[A[i]] = 1
            for j in range(i):
                if A[i]%A[j] == 0:
                    k = A[i]//A[j]
                    if k in set(A):
                        d[A[i]] += d[A[j]]*d[k]
            d[A[i]] %= 10**9+7
            ans += d[A[i]]
            ans %= 10**9+7
        # print(d)
        return ans
        # return sum(d[key] for key in d)


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        d = {}
        Aset = set(A)
        A.sort()
        ans = 0
        for i in range(len(A)):
            d[A[i]] = 1
            for j in range(i):
                if A[i]%A[j] == 0:
                    k = A[i]//A[j]
                    if k == A[j]:
                        d[A[i]] += d[A[j]]*d[A[j]]
                    elif k in set(A):
                        d[A[i]] += d[A[j]]*d[k]
            ans += d[A[i]]
            ans %= 10**9+7
        # print(d)
        return ans
        # return sum(d[key] for key in d)


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        d = {}
        Aset = set(A)
        A.sort()
        ans = 0
        for i in range(len(A)):
            d[A[i]] = 1
            for j in range(i):
                if A[i]%A[j] == 0:
                    k = A[i]//A[j]
                    if k in set(A):
                        d[A[i]] += d[A[j]]*d[k]
                        d[A[i]] %= 10**9+7
            ans += d[A[i]]
            ans %= 10**9+7
        return ans


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        SA = set(A)
        A = sorted(SA)
        C = {}
        for x in A:
            C[x] = 1
        for i, x in enumerate(A):
            for j in range(i):
                if A[j] * A[j] > A[i]:
                    break
                elif A[j] * A[j] == A[i]:
                    C[A[i]] += C[A[j]] * C[A[j]]
                elif A[i] % A[j] == 0 and A[i] // A[j] in SA:
                    C[A[i]] += 2 * C[A[j]] * C[A[i] // A[j]]
        # print(C)
        res = sum(C.values())
        return res % (10**9 + 7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        treeCount = {}

        for num in A:
            count = 1
            for p, pCount in list(treeCount.items()):
                q, rem = divmod(num, p)
                if p > q:
                    break
                if rem == 0 and q in treeCount:
                    count += pCount*treeCount[q] if p == q else 2*pCount*treeCount[q]
            treeCount[num] = count
        return sum(treeCount.values()) % (1000_000_000 + 7)


class Solution:
    def collect(self, lst, st, num, cache):
        if num in cache:
            return cache[num]
        res = 1
        for n1 in lst:
            if n1**2 > num:
                break
            if num % n1 == 0 and (num // n1) in st:
                n2 = num // n1
                res_local = self.collect(lst, st, n1, cache) * self.collect(lst, st, n2, cache)
                res += res_local
                if n1 != n2:
                    res += res_local
        mod = (10**9)+7
        res = res % mod
        cache[num] = res
        return res
    
    def solve(self, A):        
        st = set(A)
        lst = sorted(list(st))
        res = 0
        cache = {}
        mod = (10**9)+7
        for n in lst:
            res += self.collect(lst, st, n, cache)
        return res % mod
    
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        return self.solve(A)

import functools as ft
import typing as t


class Solution:
    
    BASE = 10 ** 9 + 7
    
    def divisor_pairs(self, idx: int) -> List[t.Tuple[int, int]]:
        num = self.A[idx]
        left_idx = 0
        ans = []
        while self.A[left_idx] ** 2 <= num:
            left = self.A[left_idx]
            if num % left == 0:
                right = num // left
                if right in self.A_idx:
                    ans.append((left_idx, self.A_idx[right]))
            left_idx += 1
        return ans
    
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        self.A = sorted(A)
        self.A_idx = {a: idx for idx, a in enumerate(self.A)}
        return sum(self.count_binary_trees(idx) for idx in range(len(A))) % self.BASE
    
    @ft.lru_cache(None)
    def count_binary_trees(self, idx: int) -> int:
        num = self.A[idx]
        ans = 1  # root only
        for left_idx, right_idx in self.divisor_pairs(idx):
            left_cnt = self.count_binary_trees(left_idx)
            right_cnt = self.count_binary_trees(right_idx)
            if left_idx == right_idx:
                total_cnt = left_cnt * right_cnt
            else:
                total_cnt = 2 * left_cnt * right_cnt
            ans += total_cnt
        return ans

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        d = {}
        MOD = 1000000007
        for a in A:
            d[a] = 1 + sum(d[a//b] * d[b] for b in d if not a%b and a//b in d)
        #print(d)
        return sum(d.values()) % MOD

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        mod = 10 ** 9 + 7
        A.sort()
        parents = dict()
        seen = set()
        for a in A:
            tot = 1
            for s in seen:
                if a % s == 0:
                    b = a // s
                    if b in seen:
                        tot += parents[s] * parents[b]
            parents[a] = tot
            seen.add(a)
        return sum(parents.values()) % mod
                    
                    
            


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        # Time  complexity: O(N^2)
        # Space complexity: O(N)
        # A.sort()
        # dic = {num: 1 for num in A}
        # for i in range(1, len(A)):
        #     for j in range(i):
        #         q, res = divmod(A[i], A[j])
        #         if res == 0 and q in dic:
        #             dic[A[i]] += dic[q] * dic[A[j]]

        # return sum(dic.values()) % (10**9 + 7)


        dp = {}
        for a in sorted(A):
            dp[a] = sum(dp[b] * dp.get(a // b, 0) for b in dp if a % b == 0) + 1
        return sum(dp.values()) % (10**9 + 7)


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        d = {A[0]:0}
        dp = [1]*len(A)
        MOD = 1000000007
        
        for i in range(1, len(A)):
            for j in range(0, i):
                t = A[i]//A[j]
                if t< A[j]:
                    break
                
                if not A[i] % A[j] and  t in d:
                    if A[j] == t:
                        dp[i] += dp[j] * dp[d[t]] 
                    else:
                        dp[i] += dp[j] * dp[d[t]] * 2
            
            dp[i] %= MOD
            d[A[i]] = i
            
        return sum(dp) % MOD

class Solution:
    def numFactoredBinaryTrees(self, A):
        dp = {}
        for a in sorted(A):
            dp[a] = sum(dp[b] * dp.get(a / b, 0) for b in dp if a % b == 0) + 1
        return sum(dp.values()) % (10**9 + 7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        dp = {}
        for a in sorted(A):
            dp[a] = sum(dp[b] * dp.get(a / b, 0) for b in dp if a % b == 0) + 1
        return sum(dp.values()) % (10**9 + 7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        dp = {}
        for a in sorted(A):
            dp[a] = sum(dp[b]*dp.get(a/b, 0) for b in dp if(a%b == 0))+1
        return sum(dp.values())%(10**9+7)
        


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        
        A.sort()
        A_set = set(A)
        cache = {}
        num_trees = 0
            
        # Update num trees. 
        for i, n in enumerate(A):
                        
            # Get factors pairs.
            factor_pairs = []
            for j in range(i):
                if n % A[j] == 0 and n // A[j] in A_set:
                    factor_pairs.append((n // A[j], A[j]))
                    
            # Compute num_trees.
            new_trees = 1
            for factor1, factor2 in factor_pairs:
                if factor1 != factor2:
                    new_trees += cache[factor1] * cache[factor2] # Each pair is run over twice. 
                elif factor1 == factor2:
                    new_trees += cache[factor1] * cache[factor2]
            num_trees += new_trees
            cache[n] = new_trees
            
        print(cache)    
        return num_trees % (10 ** 9 + 7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        MOD = 10 ** 9 + 7
        N = len(A)
        A.sort()
        dp = [1] * N
        index = {x: i for i, x in enumerate(A)}
        for i, x in enumerate(A):
            for j in range(i):
                if x % A[j] == 0: #A[j] will be left child
                    right = x / A[j]
                    if right in index:
                        dp[i] += dp[j] * dp[index[right]]
                        dp[i] %= MOD

        return sum(dp) % MOD

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        mod = 10**9 + 7
        A.sort()
        dp = [1 for _ in range(len(A))]
        reverse_map = {x: i for i, x in enumerate(A)}


        for i, x in enumerate(A):
            for j in range(i):
                if x % A[j] == 0: #A[j] will be left child
                    right_child = x / A[j]
                    if right_child in reverse_map:
                        dp[i] += dp[j] * dp[reverse_map[right_child]]
                        dp[i] % mod

        return sum(dp) % mod

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        
        MOD = int(1e9 + 7)
        N = len(A)
        
        A.sort()
        dp = [1] * N
        idx = {ele: i for i, ele in enumerate(A)}
        
        for c, rootVal in enumerate(A):
            for j in range(c):
                left = A[j]
                if rootVal % left == 0:
                    right = rootVal / left 
                    if right in idx:
                        dp[c] += dp[j] * dp[idx[right]] % MOD
                        
        return sum(dp) % MOD


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        
        MOD = int(1e9 + 7)
        N = len(A)
        
        A.sort()
        dp = [1] * N
        idx = {ele: i for i, ele in enumerate(A)}
        
        for i, rootVal in enumerate(A):
            for j in range(i):
                left = A[j]
                if rootVal % left == 0:
                    right = rootVal / left 
                    if right in idx:
                        dp[i] += dp[j] * dp[idx[right]]
                        dp[i] %= MOD
                        
        return sum(dp) % MOD

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        MOD = 10 ** 9 + 7
        N = len(A)
        A.sort()
        dp = [1] * N
        index = {x: i for i, x in enumerate(A)}
        for i, x in enumerate(A):
            for j in range(i):
                if x % A[j] == 0: #A[j] will be left child
                    right = x / A[j]
                    if right in index:
                        dp[i] += dp[j] * dp[index[right]]
                        dp[i] %= MOD

        return sum(dp) % MOD
            


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        O = {}
        for a in A:
            if a not in O:
                O[a] = 1
            for k, v in list(O.items()):
                if a % k == 0 and a // k in O:
                    O[a] += v * O[a // k]
        return sum(O.values()) % 1000000007


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        
        MOD = int(1e9 + 7)
        N = len(A)
        
        A.sort()
        dp = [1] * N
        idx = {ele: i for i, ele in enumerate(A)}
        
        for i, root_val in enumerate(A):
            for j in range(i):
                left = A[j]
                if root_val % left == 0:
                    right = root_val / left 
                    if right in idx:
                        dp[i] += dp[j] * dp[idx[right]]
                        dp[i] %= MOD
                        
        return sum(dp) % MOD


# 823. Binary Trees With Factors

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        
        MOD = int(1e9 + 7)
        N = len(A)
        
        A.sort()
        dp = [1] * N
        idx = {ele: i for i, ele in enumerate(A)}
        
        for c, rootVal in enumerate(A):
            for l in range(c):
                leftVal = A[l]
                if rootVal % leftVal == 0:
                    rightVal = rootVal / leftVal 
                    if rightVal in idx:
                        dp[c] += dp[l] * dp[idx[rightVal]] % MOD
                        
        return sum(dp) % MOD


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:   
        A.sort()
        numToIdx = {x : i for i, x in enumerate(A)}
        
        dp = [1 for _ in range(len(A))]
        
        MOD = 10**9 + 7
        totalSum = 0
        
        for i, x in enumerate(A):
            for j in range(i):
                y = A[j]
                if x % y == 0 and x // y in numToIdx:
                    dp[i] += dp[j] * dp[numToIdx[x // y]]
            
            totalSum = (totalSum + dp[i]) % MOD
        
        return totalSum

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A = sorted(A)
        N = len(A)
        dp = [1 for _ in range(N)]
        index_map = {}
        for index in range(N):
            index_map[A[index]] = index
        
        for k in range(N):
            for i in range(k):
                if A[k] % A[i] == 0:
                    num_to_look = A[k]//A[i]
                    if num_to_look in index_map:
                        j = index_map[num_to_look]
                        dp[k] += dp[i]*dp[j] # okay why is this not giving me the right number?
         
        return sum(dp) % (10**9 +7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        factorSet = set(A)
        A.sort()
        treeCount = {}

        for num in A:
            count = 1
            for p, pCount in list(treeCount.items()):
                q, rem = divmod(num, p)
                if p > q:
                    break
                if rem == 0 and q in treeCount:
                    tmp = pCount * treeCount[q]
                    count += tmp if p == q else 2*tmp
            treeCount[num] = count
        return sum(treeCount.values()) % (1000_000_000 + 7)


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        ret = 0
        root_value_to_tree_number = collections.defaultdict(int)
        
        
        for i in range(len(A)):
            occurrences = 1
            
            
            for j in range(i - 1, -1, -1):
                if (A[i] % A[j] == 0):
                    required_root_value = A[i] // A[j]
                    occurrences += root_value_to_tree_number[required_root_value] * root_value_to_tree_number[A[j]]
             
            root_value_to_tree_number[A[i]] = occurrences
            ret += occurrences
            
        return ret % 1000000007         

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        factors = set(A)
        A.sort()
        dp = defaultdict(int)
        count = 0
        modulus = 10**9 + 7
        for i in range(len(A)):
            dp[A[i]] += 1
            for j in range(i):
                if A[i] % A[j] == 0 and (A[i] // A[j]) in factors:
                    dp[A[i]] += dp[A[j]] * dp[A[i] // A[j]]
            count = (count + dp[A[i]]) % modulus
        return count

class Solution:
    def numFactoredBinaryTrees(self, A):
        MOD = 10 ** 9 + 7
        n = len(A)
        A.sort()
        dp = [1] * n
        index = {x: i for i, x in enumerate(A)}
        for i, x in enumerate(A):
            for j in range(i):
                if x % A[j] == 0:
                    right = x / A[j]
                    if right in index:
                        dp[i] += dp[j] * dp[index[right]]
                        dp[i] %= MOD

        return sum(dp) % MOD

import math
class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        mod = 1000000007
        dp = [1 for i in range(len(A))]
        A.sort()
        val_to_idx = {val: idx for idx, val in enumerate(A)}
        M = len(A)
        for i in range(M):
            for j in range(0, i):
 
                if A[i] % A[j] == 0 and A[i]//A[j] in val_to_idx:
                    dp[i] += (dp[j] * dp[val_to_idx[A[i]//A[j]]]) % mod
                    dp[i] = dp[i] % mod
        print(dp)
        return sum(dp) % mod
                    
            
                    
                


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        
        A.sort()
        dp = {val: 1 for val in A}
        
        for i in range(len(A)):
            for j in range(i):
                if A[i] % A[j] == 0 and A[i]//A[j] in dp:
                    dp[A[i]] += dp[A[i]//A[j]] * dp[A[j]]
        
        return sum(dp[v] for v in dp) % (10 ** 9 + 7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        n = len(A)
        A.sort()
        s = {a:i for i,a in enumerate(A)}
        d = collections.defaultdict(set)
        for i in range(n):
            for j in range(i):
                if A[i] % A[j] == 0:
                    res = A[i] // A[j]
                    if res in s:
                        d[i].add((j, s[res]))
        
        @lru_cache(maxsize=None)
        def dfs(i):
            nonlocal ans
            cur = 1
            for l, r in d[i]:
                cur += dfs(l) * dfs(r)
            return cur    
        ans = 0           
        for i in range(n):        
            val = dfs(i)        
            ans += val
        return ans % 1000000007


class Solution:
    def numFactoredBinaryTrees(self, x: List[int]) -> int:
        def f(n):
            if n in dp:return dp[n]
            ans=1
            for i in x:
                if i>(n**.5):break
                if n%i==0 and n//i in se:
                    ans+=(1 if n//i==i else 2)*f(i)*f(n//i)
            dp[n]=ans
            return ans   
        dp={}
        x.sort()
        se=set(x)
        ans=0
        for i in x:ans+=f(i)
        return ans%(10**9+7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        num_trees = {}
        A.sort()
        A_set = set(A)
        for i in range (len(A)):
            curr_num = A[i]
            num_trees[curr_num] = 1 
            for j in range (i):
                if (A[i] % A[j] == 0):
                    if (A[i] // A[j]) in A_set:
                        num_trees[curr_num] += (num_trees[A[j]] * num_trees[A[i] // A[j]])
        total = 0
        for key in num_trees:
            total += num_trees[key]
            total %= (10**9 + 7)
        return total
        


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        if not A:
            return 0

        A.sort()
        dp = {}
        for i in range(len(A)):
            dp[A[i]] = 1
            for j in range(i):
                if A[i] % A[j] == 0 and int(A[i]/A[j]) in dp:
                    dp[A[i]] += dp[A[j]] * dp[A[i]/A[j]]

        result = 0
        for key in dp:
            result += dp[key]

        return result % (10 ** 9 + 7)

def prodcount(a):
    dp =defaultdict(int)
    a.sort()
    for i in range(0,len(a)):
        dp[a[i]] = 1
        for j in range(i):
            if a[i]%a[j]==0:
                if a[i]//a[j] == a[j]:
                    dp[a[i]] += (dp[a[j]] *dp[a[i]//a[j]])
                elif dp[a[i]//a[j]]:
                    dp[a[i]] += (dp[a[j]] *dp[a[i]//a[j]])
    return sum(dp.values())% (10**9 + 7)
class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        return prodcount(A)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        memo = {}
        ans = 0
        A.sort()
        
        for i in range(len(A)):
            localAns = 1
            for j in range(i, -1, -1):
                if A[i] / A[j] in memo:
                    localAns += memo[A[i]/A[j]] * memo[A[j]]
            ans += localAns
            memo[A[i]] = localAns
        return ans % (10 ** 9 + 7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        # https://blog.csdn.net/fuxuemingzhu/article/details/83536814
        A.sort()
        dp = {}
        for i, a in enumerate(A):
            dp[a] = 1
            for j in range(i):
                if a % A[j] == 0 and a / A[j] in dp:
                    dp[a] += dp[A[j]] * dp[a / A[j]]
                    
        return sum(dp.values()) % (10**9 + 7)

class Solution:
    def numFactoredBinaryTrees(self, x: List[int]) -> int:
        def f(n):
            if n in dp:return dp[n]
            ans=0
            for i in x:
                if i==n:
                    ans+=1
                    break
                if i>n:break
                if n%i==0 and n//i in se:
                    ans+=f(i)*f(n//i)
            dp[n]=ans
            return ans   
        dp={}
        x.sort()
        se=set(x)
        ans=0
        for i in x:
            ans+=f(i)
        return ans%(10**9+7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        mapping = {x: i for i, x in enumerate(A)}
        maximal = A[-1]
        N = len(A)
        ans, MOD = [1] * N, 10 ** 9 + 7
        for i in range(N):
            for j in range(i + 1):
                if A[i] * A[j] in mapping and A[i] * A[j] <= maximal:
                    if A[i] != A[j]:
                        ans[mapping[A[i] * A[j]]] += 2 * ans[i] * ans[j]
                    else:
                        ans[mapping[A[i] * A[j]]] += ans[i] * ans[j]
                    ans[mapping[A[i] * A[j]]] %= MOD
        return sum(ans) % MOD

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        ret = 0
        root_value_to_tree_number = collections.defaultdict(int)
        
        
        for i in range(len(A)):
            occurrences = 1
            
            
            for j in range(i - 1, -1, -1):
                if (A[i] % A[j] == 0):
                    required_root_value = A[i] // A[j]
                    occurrences += root_value_to_tree_number[required_root_value] * root_value_to_tree_number[A[j]]
                    
            root_value_to_tree_number[A[i]] = occurrences
            ret += occurrences
            
        return ret % 1000000007         

class Solution:
    def numFactoredBinaryTrees(self, x: List[int]) -> int:
        def f(n):
            if n in dp:return dp[n]
            ans=1
            for i in x:
                if i>(n**.5):break
                if n%i==0 and n//i in se:
                    ans+=(1 if n//i==i else 2)*f(i)*f(n//i)
            dp[n]=ans
            return ans   
        dp={}
        x.sort()
        se=set(x)
        ans=0
        for i in x:ans+=f(i)
        return ans%(10**9+7)


class Solution(object):
    def numFactoredBinaryTrees(self, A):
        MOD = 10 ** 9 + 7
        N = len(A)
        A.sort()
        dp = [1] * N
        index = {x: i for i, x in enumerate(A)}
        for i, x in enumerate(A):
            for j in range(i):
                if x % A[j] == 0: #A[j] will be left child
                    right = x //A[j]
                    if right in index:
                        dp[i] += dp[j] * dp[index[right]]
                        dp[i] %= MOD

        return sum(dp) % MOD

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        if len(A) <= 1:
            return len(A)
        
        N, MOD = len(A), 10 ** 9 + 7
        trees = {}
        ans = 0
        A.sort()
        for i in range(N):
            trees[A[i]] = 1
            for j in range(i):
                factor = A[i]/A[j]
                if not factor.is_integer():
                    continue
                factor = int(factor)
                if factor in trees:
                    trees[A[i]] += trees[A[j]]*trees[factor] 
            ans += trees[A[i]] 
        return ans % MOD
        


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        dp = {n: 1 for n in A}
        setA = set(A)
        for i in range(len(A)): # goal
            target = A[i]
            for j in range(0, i): # using this as factor
                factor = A[j]
                if target%factor == 0:
                    other_half = target//factor
                    if other_half in setA:
                        dp[target] += dp[other_half] * dp[factor]
        return sum(dp.values())%(10**9 + 7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        n = len(A)
        nums = set(A)
        A = sorted(A)
        counts = collections.defaultdict(int)
        mod = 10**9+7
        res = 0
        for i, num in enumerate(A):
            for j in range(i):
                b, c = A[j], num/A[j]
                if c in nums:
                    counts[num] += (counts[b]*counts[c])%mod
            counts[num] += 1
            res = (res+counts[num])%mod
        return res

import math


class Solution:
    @staticmethod
    def numFactors(num, A_set):
        factors = set()
        for a in A_set:
            if num < a:
                continue
            if num % a == 0 and num // a in A_set:
                factors.add(a)
                factors.add(num // a)
        return factors

    @staticmethod
    def numFactoredTrees(root, results, A_set):
        if root in results:
            return results[root]
        factors = Solution.numFactors(root, A_set)
        # tree can only have depth 1 with the root node alone
        if len(factors) == 0:
            results[root] = 1
            return 1
        # tree can have depth greater than 1
        n = 1  # depth 1
        while len(factors) > 0:
            factor = factors.pop()
            remainder = root // factor
            if factor not in results:
                results[factor] = Solution.numFactoredTrees(factor, results, A_set)
            if factor == remainder:
                n += results[factor] * results[factor]
            else:
                factors.remove(remainder)
                if remainder not in results:
                    results[remainder] = Solution.numFactoredTrees(remainder, results, A_set)
                n += results[factor] * results[remainder] * 2
        results[root] = n
        return n

    def numFactoredBinaryTrees(self, A) -> int:
        A.sort()
        A_set = set(A)
        results = {}
        return sum([Solution.numFactoredTrees(a, results, A_set) for a in A]) % (10 ** 9 + 7)



import math


class Solution:
    @staticmethod
    def numFactors(num, A_set):
        factors = set()
        for a in A_set:
            if num % a == 0 and num // a in A_set:
                factors.add(a)
                factors.add(num // a)
        return factors

    @staticmethod
    def numFactoredTrees(root, results, A_set):
        if root in results:
            return results[root]
        factors = Solution.numFactors(root, A_set)
        # tree can only have depth 1 with the root node alone
        if len(factors) == 0:
            results[root] = 1
            return 1
        # tree can have depth greater than 1
        n = 1  # depth 1
        while len(factors) > 0:
            factor = factors.pop()
            remainder = root // factor
            if factor not in results:
                results[factor] = Solution.numFactoredTrees(factor, results, A_set)
            if factor == remainder:
                n += results[factor] * results[factor]
            else:
                factors.remove(remainder)
                if remainder not in results:
                    results[remainder] = Solution.numFactoredTrees(remainder, results, A_set)
                n += results[factor] * results[remainder] * 2
        results[root] = n
        return n

    def numFactoredBinaryTrees(self, A) -> int:
        #A.sort()
        A_set = set(A)
        results = {}
        return sum([Solution.numFactoredTrees(a, results, A_set) for a in A]) % (10 ** 9 + 7)



import math


class Solution:
    @staticmethod
    def numFactors(num, A_set):
        factors = set()
        for a in A_set:
            if num % a == 0 and num // a in A_set:
                factors.add(a)
                factors.add(num // a)
        return factors

    @staticmethod
    def numFactoredTrees(root, results, A_set):
        if root in results:
            return results[root]
        factors = Solution.numFactors(root, A_set)
        # tree can only have depth 1 with the root node alone
        if len(factors) == 0:
            results[root] = 1
            return 1
        # tree can have depth greater than 1
        n = 1  # depth 1
        while len(factors) > 0:
            factor = factors.pop()
            remainder = root // factor
            if factor not in results:
                results[factor] = Solution.numFactoredTrees(factor, results, A_set)
            if factor == remainder:
                n += results[factor] * results[factor]
            else:
                factors.remove(remainder)
                if remainder not in results:
                    results[remainder] = Solution.numFactoredTrees(remainder, results, A_set)
                n += results[factor] * results[remainder] * 2
        results[root] = n
        return n

    def numFactoredBinaryTrees(self, A) -> int:
        A.sort()
        A_set = set(A)
        results = {}
        return sum([Solution.numFactoredTrees(a, results, A_set) for a in A]) % (10 ** 9 + 7)



class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A = sorted(A)
        n = len(A)
        dict_num = {}
        for num in A:
            dict_num[num] = True
        dp_dict = {}
        factor_pair = []
        for i in range(n):
            factor_pair.append([])
        
        for i in range(n):
            for j in range(i):
                if(A[i] % A[j] == 0 and A[i]//A[j] in dict_num):
                    factor_pair[i].append((A[j], A[i]//A[j]))
        # print(factor_pair)
        for i in range(n):
            root = A[i]
            num_trees = 1
            for a, b in factor_pair[i]:
                num_trees += dp_dict[a]*dp_dict[b]
            
            dp_dict[root] = num_trees
        
        answer = 0
        for key in dp_dict:
            answer += dp_dict[key]
            
        return answer % (10**9+7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        O = {}
        ans = 0
        for a in A:
            if a not in O:
                O[a] = 1
            for k, v in list(O.items()):
                if a % k == 0 and a // k in O:
                    O[a] += v * O[a // k]
            ans += O[a]
        return ans % 1000000007



  
class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        MOD = 10 ** 9 + 7
        
        n = len(A)
        tips = sorted(A)
        
        
        index = { x: i for i, x in enumerate(tips) }
        d = [1] * n
        
        for i, x in enumerate(tips):
            head = x

            for j in range(i):
                x = tips[j]
                
                y = head // x
                
                if y*x != head:
                    continue
                if y in index:
                    leaf_1 = j
                    leaf_2 = index[y]
                    d[i] = d[i] + (d[leaf_1] * d[leaf_2])
                    
        return sum(d) % MOD

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        n = len(A)
        dp = defaultdict(int)
        res = 0
        for i, num in enumerate(A):
            dp[num] = 1
            for j in range(i):
                if num % A[j] == 0:
                    dp[num] += dp[A[j]] * dp[A[i]//A[j]]
            res += dp[num]
        return res % 1000000007


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        seen,A={},set(A)
        def find_all(root):
            if root in seen:
                return seen[root]
            combs=1
            for left in A:
                if root==left or root%left: continue
                right=root//left
                if right not in A: continue
                combs+=find_all(left)*find_all(right)
            seen[root]=combs
            return combs
        return sum(find_all(num) for num in sorted(A))%1000000007

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        mod = 10**9 + 7
        processed = dict()
        res = 0
        for a in sorted(A):
            counter = 1
            for key, val in list(processed.items()):
                key2 = a / key
                val2 = processed.get(key2, 0)
                if val2 != 0:
                    counter = (counter + val * val2) % mod
            processed[a] = counter
            res = (res + counter) % mod
        return res
            
            


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        n=len(A)
        A.sort()
        dp=[1]*n
        mod=10**9+7
        index={c:i for i,c in enumerate(A) }
        
        for i,x in enumerate(A):
            for j in range(n):
                if x%A[j]==0:
                    right=x/A[j]
                    if right in index:
                        dp[i]+=dp[j]*dp[index[right]]
                        dp[i]=dp[i]%mod
        return sum(dp)%mod

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        factorSet = set(A)
        A.sort()
        treeCount = {}

        for num in A:
            count = 1
            for p, pCount in list(treeCount.items()):
                q, rem = divmod(num, p)
                if p > q:
                    break
                if rem == 0 and q in treeCount:
                    count += pCount*treeCount[q] if p == q else 2*pCount*treeCount[q]
            treeCount[num] = count
        return sum(treeCount.values()) % (1000_000_000 + 7)


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        seen,A={},set(A)
        def find_all(root):
            if root in seen:
                return seen[root]
            combs=1
            for left in A:
                if root==left or root%left: continue
                right=root//left
                if right not in A: continue
                combs+=find_all(left)*find_all(right)
            seen[root]=combs
            return combs
        return sum(find_all(num) for num in A)%1000000007

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        dp = {i:1 for i in A}
        res = 0
        for idd, number in enumerate(A):
            
            for inner, inumber in enumerate(A[:idd]):
                if number % inumber == 0 and ((number // inumber) in dp):
                    dp[number] += dp[inumber] * dp[number // inumber]
            
            res += dp[number]
            res = res % (10 ** 9 + 7)
        
        return res


# 823. Binary Trees With Factors

MOD = 10**9 + 7

def count_binary_trees (arr):
    arr = sorted (arr)
    coll = set (arr)

    count = {}

    for index, elem in enumerate (arr):
        ans = 1
        for i in range (index):
            factor = arr[i]
            if elem % factor == 0 and elem // factor in coll:
                other_factor = elem // factor
                ans = (ans + count[factor] * count[other_factor]) % MOD

        count[elem] = ans

    return sum (y for (x, y) in count.items ()) % MOD

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        return count_binary_trees(A)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A = sorted(A)
        mems = {}
        for ix in range(len(A)):
            mems[A[ix]] = ix
            
        dp = [1] * len(A)
        
        big_mod = 10**9 + 7
        
        for i in range(len(A)):
            extras = 0
            for j in range(i):
                d, mo = divmod(A[i], A[j])
                if mo == 0:
                    if d in mems:
                        extras += dp[j] * dp[mems[d]]
                        extras = extras % big_mod

            dp[i] += extras
        
        result = sum(dp) % big_mod
        
        return result


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        # Time  complexity: O(N^2)
        # Space complexity: O(N)
        A.sort()
        dic = {num: 1 for num in A}
        for i in range(1, len(A)):
            for j in range(i):
                q, res = divmod(A[i], A[j])
                if res == 0 and q in dic:
                    dic[A[i]] += dic[q] * dic[A[j]]

        return sum(dic.values()) % (10**9 + 7)


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A = sorted(A)
        mems = {}
        for ix in range(len(A)):
            mems[A[ix]] = ix
            
        dp = [1] * len(A)
        
        big_mod = 10**9 + 7
        
        for i in range(len(A)):
            extras = 0
            for j in range(i):
                d, mo = divmod(A[i], A[j])
                if mo == 0:
                    if d in mems:
                        extras += dp[j] * dp[mems[d]]

            extras = extras % big_mod
            dp[i] += extras
        
        result = sum(dp) % big_mod
        
        return result


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        dp = {}
        mod = 10**9+7
        for a in A:
            dp[a] = 1
            for b in A:
                if a%b==0 and b in dp and a//b in dp:
                    dp[a] += dp[b]*dp[a//b]
                    dp[a] %= mod
                    
        return sum(dp.values())%mod

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        sorted_A = sorted(A)
        dp = dict()
        result = 0
        
        for i in range(len(sorted_A)):
            cur_total = 0
            for j in range(i + 1):
                cur_val = sorted_A[i]
                prev_val = sorted_A[j]
                if i == j:
                    dp[cur_val] = cur_total + 1
                    result += cur_total + 1
                elif (cur_val / prev_val) in dp:
                    cur_total += dp[cur_val/prev_val] * dp[prev_val]
                        
        return result % (10 ** 9 + 7)
                
        '''
        
        
        [18, 3, 6, 2]
        [2, 3, 6, 18]
        dp = {
            2 : 1
            3 : 1
            6 : 3
            18: 5
        }
        cur_val = 18
        prev_val = 6
        cur_total = 3 + 1 
        result = 1 + 1 + 3 + 5
        
        
        '''        
            


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        dp = {}
        for a in sorted(A):
            dp[a] = sum(dp[b] * dp.get(a/b, 0) for b in dp) + 1
        return sum(dp.values()) % (10**9 + 7)


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        ans = 0
        N = len(A)
        cnt = [1 for _ in range(N)]
        for i, n in enumerate(A):
            l, r = 0, i - 1
            while r >= l:
                if A[r] * A[l] == n:
                    cnt[i] += cnt[r] * cnt[l] if r == l else cnt[r] * cnt[l] * 2
                    l += 1
                    r -= 1
                elif A[r] * A[l] > n:
                    r -= 1
                else:
                    l += 1
            ans += cnt[i]
        return ans % (10 ** 9 + 7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        factorSet = set(A)
        A.sort()
        treeCount = {}

        for num in A:
            count = 1
            for p, pCount in list(treeCount.items()):
                q, rem = divmod(num, p)
                if rem == 0:
                    count += pCount * treeCount.get(q, 0) 
            treeCount[num] = count
        return sum(treeCount.values()) % (1000_000_000 + 7)


class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        t = {}
        for a in A:
            t[a] = 1 + sum(t[b] * t.get(a / b, 0) for b in A if b < a)
        return sum(t.values()) % (pow(10, 9) + 7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        t = {}
        for a in sorted(A):
            t[a] = 1 + sum(t[b] * t.get(a/b, 0) for b in A if b < a)
        return sum(t.values()) % (10**9 + 7)

class Solution:
    def numFactoredBinaryTrees(self, A):      
                

        t = {}
        for a in sorted(A):
            t[a] = 1 + sum(t[b] * t.get(a/b, 0) for b in A if b < a)
        return sum(t.values()) % (10**9 + 7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        mymap = {}
        for x in sorted(A):
            # 1 for leaf, plus sum any that could be factors (y and currval/y)
            mymap[x] = 1+ sum(mymap[y]*mymap.get(x/y,0) for y in A if y<x)
        return sum(mymap.values())%(10**9+7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        A.sort()
        n=len(A)
        dp=[1 for i in range(n)]
        for i in range(n):
            start,end=0,i-1
            while(start<=end):
                if A[start]*A[end]<A[i]:
                    start+=1
                    continue
                if A[start]*A[end]>A[i]:
                    end-=1
                    continue
                if start==end: 
                    dp[i]+=dp[start]*dp[end]
                else:
                     dp[i]+=dp[start]*dp[end]*2
                start+=1
                end-=1
        # print(dp)
        return sum(dp)%(10**9+7)

class Solution:
    def numFactoredBinaryTrees(self, A: List[int]) -> int:
        n = len(A)
        A.sort()
        dp = [1] * n
        res = 0
        for i in range(n):
            s = 0
            e = i - 1
            for s in range(i):
                while s <= e and A[s] * A[e] > A[i]:
                    e -= 1
                    
                if s > e:
                    break
                
                if A[s] * A[e] == A[i]:
                    dp[i] += ((dp[s] * dp[e] * 2) if s != e else (dp[s] * dp[e]))
                    dp[i] = dp[i] % (10 ** 9 + 7)
                    e -= 1
                    
            res += dp[i]
            res = res % (10 ** 9 + 7)
        
        return res