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: MEDIUM
Tags: Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

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()) % (1000000000 + 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()) % (1000000000 + 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]] %= 1000000007
				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]] %= 1000000007
		res = sum([v for (_, v) in dp.items()])
		res %= 1000000007
		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]] %= 1000000007
				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]] %= 1000000007
			res += dp[A[i]]
			res %= 1000000007
		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
		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]]
		res = sum(C.values())
		return res % (10 ** 9 + 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
		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))
		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:
		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: List[int]) -> int:
		A.sort()
		A_set = set(A)
		cache = {}
		num_trees = 0
		for (i, n) in enumerate(A):
			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]))
			new_trees = 1
			for (factor1, factor2) in factor_pairs:
				if factor1 != factor2:
					new_trees += cache[factor1] * cache[factor2]
				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:
					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:
					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(1000000000.0 + 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:
		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(1000000000.0 + 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]
		return sum(dp) % (10 ** 9 + 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


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 ** 0.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:
		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, 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:
		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)):
			target = A[i]
			for j in range(0, i):
				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)
		if len(factors) == 0:
			results[root] = 1
			return 1
		n = 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]))
		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:
		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:
		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


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:
		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.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)


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