Easy to understand memoised code
IntuitionSince this is question where we are supposed to count all possible ways , so we will use recursion to find all possible ways , and then cache the resul
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Since this is question where we are supposed to count all possible ways , so we will use recursion to find all possible ways , and then cache the results using DP.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Try to fix the root for the tree . We will give each element in the array an equal chance to be the root of the tree , so just loop over all the values in the given array. (It is guranteed that the array will never contain duplicate values.). Note that we are explicitly adding 1 too. This is for those cases when the tree contains only node, that is the root node.
2. Now , since we have to construct binary tree , we will have to find two values in the array such that there product is equal to their immediate parent. Note that we are using a map here , but that is only because we cannot the values in the array directly since they are of the range 1e9 , so we have to work with the indices.
3. Now comes the main idea.
 The idea is that we will try to fix the left subtree , and try to find all the possible number of trees by only expanding the right subtree. 
You might ask , we can also do the opposite , wherein we fix the right subtree and only try to expand the left subtree.
Well , you are right in thinking that , but if you look closely , that is already taken care of since we are iterating for every value in map , so for every pair (left,right) , we will also consider the pair (right,left) because of the loop.
Ex : 6 = 2 * 3
Now , lets say we encounter 2 first , so we consider left=2 and right=3. After we done counting , we will encounter 3. In this case , 3 become left , and 2 becomes right . 
Note that this will even work if values of left and right are same ( like 16 = 4*4)
4. Just remeber to cache the recursion with DP in order to avoid TLE.
# Complexity
- Time complexity: O(N^2)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->


# Code
```cpp []
class Solution {
public:
typedef long long ll;
    const ll mod=1e9+7;
    
    unordered_map<ll,ll>m;
    vector<int>v;
    int dp[1005];
    ll f(int i){
        // for every parent , we need to find 2 values s.t their product is equal to parent
        if(dp[i]!=-1) return dp[i];
        ll parent = v[i];
        ll cnt=0;
        for(auto &[j,k] : m){
            if(parent%j==0 and m.find(parent/j)!=m.end()){
                
                ll left = j;
                ll right = parent/j;
                ll lways=0,rways=0;
                lways = (f(m[left])%mod+1)%mod;
                rways = (f(m[right])%mod+1)%mod;
                cnt=(cnt%mod+ ((ll)(lways%mod)*(ll)(rways%mod))%mod)%mod;
            }
        }
        return dp[i]=cnt;

    }
    int numFactoredBinaryTrees(vector<int>& nums) {
        memset(dp,-1,sizeof(dp));
        ll n=nums.size();
        ll cnt=0;
        v=nums;
        for(int i=0;i<n;i++){
            m[nums[i]]=i;
        }
        for(int i=0;i<n;i++){
            // assume that nums[i] is the main root of the binary tree
            cnt = (cnt%mod + f(i)%mod)%mod;
            cnt=(cnt%mod+1)%mod; // this case is when we are only taking one element in the tree , i.e nums[i];
        }
        return cnt;
    }
};
```
['C++']