Given an integer array A, and an integer target, return the number of tuples i, j, k  such that i < j < k and A[i] + A[j] + A[k] == target.
As the answer can be very large, return it modulo 109 + 7.
Example 1:
Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: 
Enumerating by the values (A[i], A[j], A[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.
Example 2:
Input: A = [1,1,2,2,2,2], target = 5
Output: 12
Explanation: 
A[i] = 1, A[j] = A[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.
Constraints:
3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300
class Solution:
    def threeSumMulti(self, A: List[int], target: int) -> int:
        counter = collections.Counter(A)
        i, res, l, ckey = 0, 0, len(counter), sorted(list(counter.keys()))
        if target % 3 == 0:
            res += math.comb(counter[target // 3], 3)
        for i in range(l):
            ni = ckey[i]
            nk = target - (2 * ni)
            if ni != nk and nk >= 0:
                res += math.comb(counter[ni], 2) * counter[nk]
        for i in range(l):
            for j in range(i + 1, l):
                ni, nj = ckey[i], ckey[j]
                nk = target - ni - nj
                if ni < nj < nk <= 100:
                    res += counter[ni] * counter[nj] * counter[nk]
        return res % (10**9 + 7)
        # while i < l:
        #     j = i
        #     while j < l:
        #         ni, nj = ckey[i], ckey[j]
        #         nk = target - ni - nj
        #         if ni == nk == nj:
        #             res += math.comb(counter[ni], 3)
        #         elif nj == nk:
        #             res += math.comb(counter[nj], 2) * counter[ni]
        #         elif ni == nk:
        #             res += math.comb(counter[nk], 2) * counter[nj]
        #         elif ni == nj:
        #             res += math.comb(counter[ni], 2) * counter[nk]
        #         else:
        #             res += counter[ni] * counter[nj] * counter[nk]
        #         print(ni, nj, nk, res)
        #         j += 1
        #     i += 1
        # return res % (10**9 + 7)

class Solution:
    def threeSumMulti(self, A: List[int], target: int) -> int:
        counter = collections.Counter(A)
        i, res, l, ckey = 0, 0, len(counter), sorted(list(counter.keys()))
        if target % 3 == 0:
            res += math.comb(counter[target // 3], 3)
        for i in range(l):
            ni = ckey[i]
            nk = target - (2 * ni)
            if ni != nk and nk >= 0:
                res += math.comb(counter[ni], 2) * counter[nk]
        for i in range(l):
            for j in range(i + 1, l):
                ni, nj = ckey[i], ckey[j]
                nk = target - ni - nj
                if ni < nj < nk <= 100:
                    res += counter[ni] * counter[nj] * counter[nk]
        return res % (10**9 + 7)
        # while i < l:
        #     j = i
        #     while j < l:
        #         ni, nj = ckey[i], ckey[j]
        #         nk = target - ni - nj
        #         if ni == nk == nj:
        #             res += math.comb(counter[ni], 3)
        #         elif nj == nk:
        #             res += math.comb(counter[nj], 2) * counter[ni]
        #         elif ni == nk:
        #             res += math.comb(counter[nk], 2) * counter[nj]
        #         elif ni == nj:
        #             res += math.comb(counter[ni], 2) * counter[nk]
        #         else:
        #             res += counter[ni] * counter[nj] * counter[nk]
        #         print(ni, nj, nk, res)
        #         j += 1
        #     i += 1
        # return res % (10**9 + 7)
