Python [DP]
As we are counting a large number of trees it\'s not a surprise this is dynamic programming. There\'s some structure in the problem and we need to represent in 
As we are counting a large number of trees it\'s not a surprise this is dynamic programming. There\'s some structure in the problem and we need to represent in in our DP. Here is how it proceeds: First sort the array (they don\'t sort it for you, so help yourself). \n\nNow at every step we want to find the number of trees that end at value `x`. For that we consider every `y < x`. If `z = x//y` is such that `z*y = x` we can have `dp[y]*dp[z]` amount of trees that have children `y` and `z` and root `x`. Furthermore the set of `y,z` we consider are disjoint so we can sum them up to find all trees that end at root `z`. We used the two basic rules of counting: sum and product rules. It is important to note the pairs of `y,z` are disjoint, so that we can use simple summation (and not the Principle of Inclusion and Exclusion). We are left with one final question: we have `x`, we have `y`. How can we quickly access the counts for `z`? If we use the python built-in defaultdict, then if `z` cannot be achieved its count will be 0 and the product will evaluate to 0. This leads to the following short solution.\n\nIt\'s trickier than it appears...\n\nNote: Also the question statement is ambiguous, as if you have a tree like `7 -> 7 -> 7 -> ... ` the one-children "product" is always the same as root, and the solution is always infinite. So it has to be noted that to be a valid product you need to have both children nodes. \n\n```python\nclass Solution:\n    def numFactoredBinaryTrees(self, arr):\n        arr.sort()\n        \n        dp = collections.defaultdict(int)\n        for x in arr:\n            dp[x] = 1\n        \n        for i in range(1, len(arr)):\n            for j in range(i):\n                x, y, z = arr[i], arr[j], arr[i]//arr[j]\n                if y*z == x:\n                    dp[x] += dp[y]*dp[z]\n                \n        return sum(dp.values()) % (10**9 + 7)\n```
[]