<p>Given an array of unique integers, <code>arr</code>, where each integer <code>arr[i]</code> is strictly greater than <code>1</code>.</p>

<p>We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node&#39;s value should be equal to the product of the values of its children.</p>

<p>Return <em>the number of binary trees we can make</em>. The answer may be too large so return the answer <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [2,4]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can make these trees: <code>[2], [4], [4, 2, 2]</code></pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [2,4,5,10]
<strong>Output:</strong> 7
<strong>Explanation:</strong> We can make these trees: <code>[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]</code>.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 1000</code></li>
	<li><code>2 &lt;= arr[i] &lt;= 10<sup>9</sup></code></li>
	<li>All the values of <code>arr</code> are <strong>unique</strong>.</li>
</ul>

#define ll long long 
class Solution {
const int M=(int)(1e9+7);
int modadd(int a,int b)
{
    return ((a%M)+(b%M))%M;
}
int modmul(int a,int b)
{
    return (1LL*a*b)%M;
}
public:
    int numFactoredBinaryTrees(vector<int>& a) {
        sort(a.begin(),a.end());
        unordered_map<int,vector<pair<int,int>>> m;
        int n=a.size();
        if(n==1)
        {
            return 1;
        }
        for(int i=1;i<n;i++)
        {
            int f=0;int l=i-1; 
            while(f<=l)
            {
                ll p=1LL*a[f]*a[l];
                if(p<a[i])
                {
                    f++;
                }
                else if(p>a[i])
                {
                    l--;
                }
                else
                {
                    m[a[i]].push_back({a[f],a[l]});
                    f++;
                    l--;
                }
            }
        }
        unordered_map<int,int> dp;
        int ans=0;
        for(int i=0;i<n;i++)
        {
            dp[a[i]]++;
            for(auto &j:m[a[i]])
            {
                int x=j.first;
                int y=j.second;
                if(x==y)
                dp[a[i]]=modadd(dp[a[i]],modmul(dp[x],dp[y]));
                else 
                dp[a[i]]=modadd(dp[a[i]],modmul(2,modmul(dp[x],dp[y])));
            }
            ans=modadd(ans,dp[a[i]]);
        }
        return ans;
        // for(auto i:m)
        // {
        //     cout<<i.first<<endl;
        //     for(auto &j:i.second)
        //     {
        //         cout<<j.first<<" "<<j.second<<endl;
        //     }
        // }
        return 0;

    }   
};
14700