Given an array of unique integers, arr, where each integer arr[i] 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 its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 109 + 7.

&nbsp;
Example 1:

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

Input: arr = [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].

&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 1000
	2 &lt;= arr[i] &lt;= 109
	All the values of arr are unique.


class Solution:
    def numFactoredBinaryTrees(self, nums: List[int]) -> int:
        nums = set(nums)
        n = len(nums)
        
        @lru_cache(None)
        def helper(num):
            trees = 1
            for factor in nums:
                if not num % factor and num // factor in nums:
                    trees += helper(factor) * helper(num // factor)

            return trees
        
        return sum(helper(num) for num in nums) % (10 ** 9 + 7)
class Solution {
    int mod = 1000000007;
    HashMap<Integer, Long> dp;
    HashSet<Integer> set;
    
    public int numFactoredBinaryTrees(int[] arr) {
        long ans = 0;
        dp = new HashMap<>();
        set = new HashSet<>();
        
        for(int val : arr) set.add(val);
        
        for(int val : arr) {
			//giving each unique value a chance to be root node of the tree
            ans += solve(val, arr);
            ans %= mod;
        }
        
        return (int)ans;
    }
    
    public long solve(int val, int[] nums) {
        
        if(dp.containsKey(val)) {
            return dp.get(val);
        }
        
        long ans = 1;
        
        for(int i = 0; i < nums.length; i++) {
            if(val % nums[i] == 0 && set.contains(val / nums[i])) {
                long left = solve(nums[i], nums);
                long right = solve(val / nums[i], nums);
                
                ans += ((left * right) % mod);
                ans %= mod;
            }
        }
        
        dp.put(val, ans);
        
        return ans;
    }
}
class Solution {
public:
    const int mod=1e9+7;
    int numFactoredBinaryTrees(vector<int>& arr) {

        sort(arr.begin(),arr.end());
        int n=arr.size();

        vector<int> dp(n,1);

        for(int i=1;i<n;i++){
            int l=0,r=i-1;
            while(l<=r){
                if(arr[l]*1LL*arr[r]==arr[i]*1LL){
                    if(l!=r) dp[i]=(dp[i]+(dp[l]*1LL*dp[r]%mod*2LL%mod))%mod;
                    else dp[i]=(dp[i]+(dp[l]*1LL*dp[r]%mod))%mod;
                    l++,r--;
                } else if(arr[l]*1LL*arr[r]>arr[i]*1LL) r--;
                else l++;
            }
        }

        int ans=0;
        for(auto i:dp) ans=(ans+i)%mod;
        return ans;
    }
};
/** https://leetcode.com/problems/binary-trees-with-factors/
 * @param {number[]} arr
 * @return {number}
 */
var numFactoredBinaryTrees = function(arr) {
  // Memo
  this.memo = new Map();
  
  // Sort the `arr`
  arr.sort((a, b) => a - b);
  
  // Create hashmap so we can easily find the index of the value
  let map = new Map();
  arr.forEach((val, idx) => map.set(val, idx));
  
  // We are going to calculate total numbers of binary trees by assigning each `arr[i]` as the root of the tree
  let count = 0;
  for (let i = arr.length - 1; i >= 0; i--) {
    count += dp(arr, map, i);
  }
  
  // Perform mod on the final result
  let mod = (10 ** 9) + 7;
  return count % mod;
};

var dp = function(arr, map, currIdx) {
  // Return from memo
  if (this.memo.has(currIdx) === true) {
    return this.memo.get(currIdx);
  }
  
  // Start the count as 1 to include the current node
  let count = 1;
  
  // Loop through all number before `arr[currIdx]`
  for (let i = currIdx - 1; i >= 0; i--) {
    // The `left` and `right` node of the root
    // The `right` node is basically the root divided by the `left` since the rule stated that the root is product of its children
    let left = arr[i];
    let right = arr[currIdx] / left;
    
    // Ignore if the root is not a product of its children
    if (arr[currIdx] % left !== 0 ||
       map.has(right) === false) {
      continue;
    }
    
    // Get the count for `left` node and `right` node
    let leftCount = dp(arr, map, i);
    let rightCount = dp(arr, map, map.get(right));
    
    // Total count is multiplication of `left` and `right` count because each combination of is unique
    count += leftCount * rightCount;
  }
  
  // Set memo
  this.memo.set(currIdx, count);
  
  return count;
};
Binary Trees With Factors