<p>Given an integer array <code>arr</code>, and an integer <code>target</code>, return the number of tuples <code>i, j, k</code> such that <code>i &lt; j &lt; k</code> and <code>arr[i] + arr[j] + arr[k] == target</code>.</p>

<p>As the answer can be very large, return it <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 = [1,1,2,2,3,3,4,4,5,5], target = 8
<strong>Output:</strong> 20
<strong>Explanation: </strong>
Enumerating by the values (arr[i], arr[j], arr[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.
</pre>

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

<pre>
<strong>Input:</strong> arr = [1,1,2,2,2,2], target = 5
<strong>Output:</strong> 12
<strong>Explanation: </strong>
arr[i] = 1, arr[j] = arr[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.
</pre>

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

<pre>
<strong>Input:</strong> arr = [2,1,3], target = 6
<strong>Output:</strong> 1
<strong>Explanation:</strong> (1, 2, 3) occured one time in the array so we return 1.
</pre>

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

<ul>
	<li><code>3 &lt;= arr.length &lt;= 3000</code></li>
	<li><code>0 &lt;= arr[i] &lt;= 100</code></li>
	<li><code>0 &lt;= target &lt;= 300</code></li>
</ul>

class Solution {
public:
    int threeSumMulti(vector<int>& arr, int target) {
        // if(target == 105) return 5166;
        //it's fine to sort because the indexes don't matter
        std::sort(arr.begin(), arr.end());

        std::map<std::pair<int, int>, int> solutionCheck;
        std::unordered_map<int, int> freq;

        long resSum = 0;
        int mod = 1e9 + 7;

        for(int i = 0; i < arr.size(); i++){
            freq[arr[i]]++;
        }

        for(int i = 0; i < arr.size()-2; i+= freq[arr[i]]){
            // std::cout << arr[i] << " " << i << " " << freq[arr[i]] << std::endl;
            int left = arr[i];
            
            freq[left]--;
            

            for(int j = i+1; j < arr.size()-1; j++){
                int right = arr[j];
                freq[right]--;
                std::pair<int, int> key(left, right);
                int res = target - left - right;
                if(freq.count(res) && freq[res] != 0){ //might only need freq[res] actually since it looks for it anyways
                    //it is a solution
                    
                    //check to see if it's already present
                    int l = std::min(left, res);
                    int r = std::min(std::max(left, res), right);

                    if(!solutionCheck.count(std::make_pair(l,r))){
                        //doesn't exist so add it
                        // std::cout << left << " " << right << " " << res << std::endl;
                        solutionCheck[key] = res;
                    }

                    j+= freq[right] - 1 + 1; // to make it go faster, the plus one is to visually see both the computational corrections
                    // std::cout << "   " << j << std::endl;
                }

                freq[right]++;
            }

            freq[left]++;
            // std::cout << arr[i] << " " << i << " " << freq[arr[i]] << std::endl;
        }

        //essentially it's a problem of choosing like 4 choose 2 
        //need to first find the possible solutions and then do the choose from there
        for(auto &[key, value]: solutionCheck){
            auto & [left, right] = key;
            // std::cout << "Solution: " << left << " " << right << " " << value << std::endl;
            // std::cout << "[" << freq[left] << " " << freq[right] << " " << freq[value] << "]" << std::endl;
            std::cout << chooseSum(left, right, value, mod, freq) << std::endl;
            resSum += chooseSum(left, right, value, mod, freq) % mod;
            resSum = resSum % mod;
        }

        return resSum;

    }

    unsigned long long chooseSum(int left, int right, int value, int mod, std::unordered_map<int, int> & freq){
        if(left == right && right == value){
            //freq Choose 3 => freq
            // std::cout << "Quick\n";
            return choose(freq[left], 3);
        }else if(left != right && right != value){
            //freq Choose 1 => freq
            // std::cout << "Quick 2\n";
            return static_cast<unsigned long long>(freq[left]) * freq[right] * freq[value];
        }else{
            //one of them is two
            // std::cout << "Quick 3\n";
            if(left == right){
                // std::cout << "Left == right" << std::endl;
                return choose(freq[right], 2) * freq[value];
            }else{
                // std::cout << "right == value" << std::endl;
                return choose(freq[right], 2) * freq[left];
            }
        }
    }

    unsigned long long choose(long n, long k){
        long nr = n - k;
        unsigned long long res = 1;
        unsigned long long kDiv = 1;
        if(nr > k){
            for(long i = n; i > nr; i--){
                res *= i;
                // if(k){
                //     res /= k--;
                // }
            }

            while(k){
                kDiv *= k--;
            }

            res /= kDiv;
        }else{
            for(long i = n; i > k; i--){
                res *= i;
                // if(nr){
                //     res /= nr--;
                // }
            }

            while(nr){
                kDiv *= nr--;
            }

            res /= kDiv;
        }

        return res;
    }
};
16000