#
# import collections
# 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 10^9 + 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.
#
#
# Note:
#
# 3 <= A.length <= 3000
# 0 <= A[i] <= 100
# 0 <= target <= 300


class Solution(object):
    def threeSumMulti(self, A, target):
        """
        :type A: List[int]
        :type target: int
        :rtype: int
        """
        d, res, modeN = collections.Counter(A), 0, 10 ** 9 + 7
        nums_2 = [x[0] for x in d.items() if x[1] > 1]
        nums_new = sorted([x[0] for x in d.items()])

        n = target / 3
        if n in d:
            if 3 * n == target:
                m = d[target / 3]
                res += (m * (m - 1) * (m - 2) / 6) % modeN

        rtn = []

        for i, j in enumerate(nums_new):
            numss2 = nums_new[i + 1:]
            for x, y in enumerate(numss2):
                if target - j - y in [j, y] and target - j - y in nums_2:
                    if sorted([j, y, target - j - y]) not in rtn:
                        rtn.append(sorted([j, y, target - j - y]))
                        m = d[target - j - y]
                        if target - j - y == j:
                            n = d[y]
                        else:
                            n = d[j]
                        res += (m * (m - 1) * n / 2) % modeN

                if target - j - y not in [j, y] and target - j - y in nums_new:
                    if sorted([j, y, target - j - y]) not in rtn:
                        rtn.append(sorted([j, y, target - j - y]))
                        res += d[j] * d[y] * d[target - j - y] % modeN

        return res


if __name__ == '__main__':
    # print Solution().threeSumMulti([1, 1, 2, 2, 3, 3, 4, 4, 5, 5], 8)
    # print Solution().threeSumMulti([1, 1, 2, 2, 2, 2], 5)
    print Solution().threeSumMulti([0, 2, 0, 0], 2)
    print Solution().threeSumMulti([0, 0, 0], 0)
    print Solution().threeSumMulti(
        [35, 29, 93, 59, 16, 53, 90, 88, 2, 28, 40, 83, 60, 92, 22, 18, 70, 42, 50, 73, 10, 23, 17, 3, 48, 51, 29, 16,
         42, 33, 51, 34, 13, 38, 54, 59, 19, 92, 60, 81, 69, 90, 80, 1, 12, 72, 79, 1, 67, 63, 13, 2, 61, 65, 16, 19,
         20, 52, 19, 68, 11, 90, 9, 77, 29, 91, 78, 42, 66, 41, 67, 97, 79, 0, 49, 6, 84, 37, 59, 93, 23, 40, 16, 0, 46,
         74, 62, 97, 96, 99, 53, 84, 99, 14, 82, 21, 24, 43, 7, 11, 41, 96, 19, 8, 8, 45, 60, 57, 16, 26, 54, 64, 83,
         95, 29, 42, 43, 27, 14, 4, 52, 76, 41, 20, 7, 27, 3, 39, 26, 49, 18, 31, 51, 63, 88, 94, 46, 27, 40, 16, 46,
         29, 93, 18, 39, 35, 100, 4, 29, 81, 9, 37, 21, 9, 53, 30, 58, 78, 41, 77, 30, 50, 16, 84, 59, 53, 40, 90, 4,
         85, 53, 89, 62, 27, 1, 2, 31, 79, 47, 76, 9, 82, 86, 76, 5, 55, 100, 77, 64, 35, 70, 100, 59, 47, 35, 70, 59,
         93, 59, 98, 14, 31, 30, 12, 26, 13, 7, 16, 3, 76, 23, 46, 39, 81, 25, 5, 70, 73, 7, 35, 71, 18, 66, 60, 86, 63,
         97, 32, 14, 35, 68, 69, 31, 52, 83, 34, 100, 40, 44, 7, 28, 76, 38, 90, 36, 34, 10, 99, 47, 49, 63, 74, 5, 53,
         11, 99, 33, 46, 78, 36, 51, 26, 43, 83, 9, 68, 31, 48, 71, 53, 64, 64, 43, 62, 77, 59, 100, 84, 15, 23, 95, 5,
         6, 7, 23, 20, 84, 60, 75, 25, 63, 54, 94, 83, 52, 16, 26, 48, 40, 75], 138)
