923

class Solution {
public:
    int threeSumMulti(vector<int>& A, int target) {
        unordered_map<int, long> c;
        for(int n : A) c[n]++;
        long res = 0;
        for(auto it : c)
            for(auto it2 : c){
                int i = it.first, j = it2.first, k = target - i - j;
                if (!c.count(k)) continue;
                if (i == j && j == k)
                    res += c[i] * (c[i] - 1) * (c[i] - 2) / 6;
                else if (i == j && j != k)
                    res += c[i] * (c[i] - 1) / 2 * c[k];
                else if (i < j && j < k)
                    res += c[i] * c[j] * c[k];
            }
        return res % int(1e9 + 7);
    }
};