solution.py

class Solution:
    def threeSumMulti(self, A: List[int], target: int) -> int:
        cnt = collections.Counter(A)
        res = 0
        MOD = 10**9+7
        for a, b, c in itertools.combinations(cnt.keys(), 3):
            if a+b+c == target:
                res += cnt[a]*cnt[b]*cnt[c] % MOD
        for a, b in itertools.combinations(cnt.keys(), 2):
            if 2*a+b==target and cnt[a]>=2:
                res += (cnt[a]*(cnt[a]-1)//2)*cnt[b] % MOD
            if a+2*b==target and cnt[b]>=2:
                res += (cnt[b]*(cnt[b]-1)//2)*cnt[a] % MOD
        for a in cnt.keys():
            if 3*a == target and cnt[a]>=3:
                res += (cnt[a]*(cnt[a]-1)*(cnt[a]-2))//6
        return res%MOD