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

Difficulty: MEDIUM
Tags: Data structures

Sorting

Amortized analysis

Mathematics
Skill types: Amortized analysis

Sorting

Data structures

Starter code:
class Solution:
    def threeSumMulti(self, A: List[int], target: int) -> int:
        

Solutions:
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)


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		d = Counter(A)
		keys = sorted(d.keys())
		count = 0
		for (i, a) in enumerate(keys):
			if a <= target // 3:
				for b in keys[i + 1:]:
					if target - a - b <= b:
						break
					elif target - a - b in d:
						count += d[a] * d[b] * d[target - a - b]
			else:
				break
		for k in keys:
			if target != 3 * k and target - 2 * k in d:
				count += math.comb(d[k], 2) * d[target - 2 * k]
		if 3 * (target // 3) == target:
			count += math.comb(d[target // 3], 3)
		return count % (10 ** 9 + 7)


class Solution(object):

	def threeSumMulti(self, A, target):
		count = [0] * 101
		ans = 0
		for n in A:
			count[n] += 1
		for x in range(101):
			for y in range(x + 1, 101):
				z = target - x - y
				if x < y < z <= 100:
					ans += count[x] * count[y] * count[z]
					ans %= 10 ** 9 + 7
		for x in range(101):
			z = target - 2 * x
			if 0 <= z <= 100 and x != z:
				ans += count[x] * (count[x] - 1) // 2 * count[z]
				ans %= 10 ** 9 + 7
		if not target % 3:
			x = target // 3
			if 0 <= x <= 100:
				ans += count[x] * (count[x] - 1) * (count[x] - 2) // 6
				ans %= 10 ** 9 + 7
		return ans


from collections import Counter

class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		MAX = 10 ** 9 + 7
		count = collections.Counter(A)
		keys = sorted(count)
		ans = 0
		for (i, x) in enumerate(keys):
			j = i
			k = len(keys) - 1
			while j <= k:
				(y, z) = (keys[j], keys[k])
				sum_t = x + y + z
				if sum_t < target:
					j += 1
				elif sum_t > target:
					k -= 1
				else:
					if i < j < k:
						ans += count[x] * count[y] * count[z]
					elif x == y and y < z:
						ans += count[x] * (count[x] - 1) * count[z] // 2
					elif x < y and y == z:
						ans += count[x] * count[y] * (count[y] - 1) // 2
					else:
						ans += count[x] * (count[x] - 1) * (count[x] - 2) // 6
					j += 1
					k -= 1
		return ans % MAX


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		(cnt, res) = (collections.Counter(A), 0)
		for i in cnt:
			for j in cnt:
				k = target - i - j
				if i == j == k:
					res += cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) // 6
				elif i == j:
					res += cnt[i] * (cnt[i] - 1) // 2 * cnt[k]
				elif i < j < k:
					res += cnt[i] * cnt[j] * cnt[k]
				res = res % (10 ** 9 + 7)
		return res


class Solution(object):

	def threeSumMulti(self, A, target):
		MOD = 10 ** 9 + 7
		count = collections.Counter(A)
		keys = sorted(count)
		ans = 0
		for (i, x) in enumerate(keys):
			T = target - x
			(j, k) = (i, len(keys) - 1)
			while j <= k:
				(y, z) = (keys[j], keys[k])
				if y + z < T:
					j += 1
				elif y + z > T:
					k -= 1
				else:
					if i < j < k:
						ans += count[x] * count[y] * count[z]
					elif i == j < k:
						ans += count[x] * (count[x] - 1) // 2 * count[z]
					elif i < j == k:
						ans += count[x] * count[y] * (count[y] - 1) // 2
					else:
						ans += count[x] * (count[x] - 1) * (count[x] - 2) // 6
					j += 1
					k -= 1
		return ans % MOD


from collections import Counter

class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		MOD = 10 ** 9 + 7
		if len(A) < 3:
			return 0
		counts = Counter(A)
		keys = sorted(counts.keys())
		(n, res) = (len(keys), 0)
		for (i, a) in enumerate(keys):
			T = target - a
			(j, k) = (i, n - 1)
			while j <= k:
				(b, c) = (keys[j], keys[k])
				if b + c < T:
					j += 1
				elif b + c > T:
					k -= 1
				else:
					if i < j < k:
						res += counts[a] * counts[b] * counts[c]
					elif i == j < k:
						res += counts[a] * (counts[a] - 1) // 2 * counts[c]
					elif i < j == k:
						res += counts[a] * counts[b] * (counts[b] - 1) // 2
					else:
						res += counts[a] * (counts[a] - 1) * (counts[a] - 2) // 6
					j += 1
					k -= 1
		return res % MOD


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		count = collections.Counter(A)
		valuelist = list(count.keys())
		valuelist.sort()
		res = 0
		for i in range(len(valuelist)):
			for j in range(i, len(valuelist)):
				a = valuelist[i]
				b = valuelist[j]
				c = target - a - b
				if c not in count:
					continue
				if a == b == c:
					res += count[a] * (count[a] - 1) * (count[a] - 2) // 6
				elif a == b and b != c:
					res += count[a] * (count[a] - 1) // 2 * count[c]
				elif a < b and b < c:
					res += count[a] * count[b] * count[c]
		return res % (10 ** 9 + 7)


import collections as clc
import itertools as it

class Solution:
	BASE = 10 ** 9 + 7

	def threeSumMulti(self, A: List[int], target: int) -> int:
		counter = clc.Counter(A)
		values = sorted(counter)
		n = len(values)
		pair_sums = clc.Counter()
		ans = 0
		for k in range(n):
			if 3 * values[k] == target and counter[values[k]] >= 3:
				cnt = counter[values[k]]
				ans = (ans + cnt * (cnt - 1) * (cnt - 2) // 6) % self.BASE
		for (j, k) in it.combinations(range(n), 2):
			if 2 * values[j] + values[k] == target and counter[values[j]] >= 2:
				cntj = counter[values[j]]
				cntk = counter[values[k]]
				ans = (ans + cntj * (cntj - 1) // 2 * cntk) % self.BASE
			if values[j] + 2 * values[k] == target and counter[values[k]] >= 2:
				cntj = counter[values[j]]
				cntk = counter[values[k]]
				ans = (ans + cntk * (cntk - 1) // 2 * cntj) % self.BASE
		for k in range(2, n):
			j = k - 1
			for i in range(j):
				pair_sums[values[i] + values[j]] += counter[values[i]] * counter[values[j]]
			ans = (ans + counter[values[k]] * pair_sums[target - values[k]]) % self.BASE
		return ans % self.BASE


from collections import Counter

class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		countA = Counter(A)
		ans = 0
		done = set()
		M = int(1000000000.0 + 7)
		for (i, j) in list(countA.items()):
			for (k, l) in list(countA.items()):
				req = target - i - k
				temp = tuple(sorted([i, k, req]))
				if temp not in done:
					done.add(temp)
					if i == k == req:
						ans += j * (j - 1) * (j - 2) // 6
					if i == k and i != req:
						ans += j * (j - 1) // 2 * countA[req]
					if i != k and i == req:
						ans += l * (j * (j - 1)) // 2
					if i != k and k == req:
						ans += j * (l * (l - 1)) // 2
					if i != k and k != req:
						ans += j * l * countA[req]
					ans %= M
		return ans


class Solution:

	def threeSum(self, A: List[int], target: int) -> List[List[int]]:
		triples = []
		i = 0
		k = len(A) - 1
		while i <= k:
			j = i
			k = len(A) - 1
			while j <= k:
				if A[j] + A[k] < target - A[i]:
					j += 1
				elif A[j] + A[k] > target - A[i]:
					k -= 1
				else:
					triples.append([A[i], A[j], A[k]])
					j += 1
					k -= 1
			i += 1
		return triples

	def threeSumMulti(self, A: List[int], target: int) -> int:
		res = 0
		count = {}
		for num in A:
			count[num] = count.get(num, 0) + 1
		sorted_A_no_dup = sorted([num for num in count])
		all_triples = self.threeSum(sorted_A_no_dup, target)
		for triple in all_triples:
			(a, b, c) = (triple[0], triple[1], triple[2])
			if a != b and b != c:
				res += count[a] * count[b] * count[c]
			elif a == b and b != c:
				res += count[a] * (count[a] - 1) * count[c] // 2
			elif a != b and b == c:
				res += count[a] * count[b] * (count[b] - 1) // 2
			elif a == b and b == c:
				res += count[a] * (count[a] - 1) * (count[a] - 2) // 6
			res %= 10 ** 9 + 7
		return res


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		ADict = {}
		A = sorted(A)
		print(A)
		for a in A:
			if a in ADict:
				ADict[a] += 1
			else:
				ADict[a] = 1
		ijSame = False
		keys = sorted(ADict)
		totWays = 0
		for i in range(len(keys)):
			if keys[i] > target:
				break
			elif ADict[keys[i]] < 3:
				continue
			elif keys[i] * 3 == target:
				numOcc = ADict[keys[i]]
				totWays += numOcc * (numOcc - 1) * (numOcc - 2) / 6
		if len(keys) == 1:
			return int(totWays % (10 ** 9 + 7))
		for i in range(len(keys)):
			if keys[i] > target:
				break
			elif ADict[keys[i]] < 2:
				continue
			else:
				sum = keys[i] * 2
				remain = target - sum
				if not remain == keys[i] and remain in keys:
					numDoubleOcc = ADict[keys[i]]
					numSingleOcc = ADict[remain]
					totWays += numDoubleOcc * (numDoubleOcc - 1) / 2 * numSingleOcc
		if len(keys) == 2:
			return int(totWays % (10 ** 9 + 7))
		for i in range(len(keys)):
			if keys[i] > target:
				break
			for j in range(i + 1, len(keys)):
				sum = keys[i] + keys[j]
				if sum > target:
					break
				remaining = target - sum
				if remaining in keys[j + 1:]:
					totWays += ADict[keys[i]] * ADict[keys[j]] * ADict[remaining]
		return int(totWays % (10 ** 9 + 7))


class Solution:

	def calculate_weight(self, x, y, z, freq):
		if x == y and y == z:
			return freq[x] * (freq[x] - 1) * (freq[x] - 2) // 6
		if x == y:
			return freq[x] * (freq[x] - 1) // 2 * freq[z]
		if x == z:
			return freq[x] * (freq[x] - 1) // 2 * freq[y]
		if y == z:
			return freq[z] * (freq[z] - 1) // 2 * freq[x]
		return freq[x] * freq[y] * freq[z]

	def calculate_freq(self, A):
		freq = {}
		for k in A:
			if k in list(freq.keys()):
				freq[k] += 1
			else:
				freq[k] = 1
		return freq

	def threeSumMulti(self, A: List[int], target: int) -> int:
		freq = self.calculate_freq(A)
		unique_values = list(freq.keys())
		count = 0
		two_sum_combinations = {}
		for x in unique_values:
			for y in unique_values:
				maxval = max(x, y)
				minval = min(x, y)
				if x + y not in two_sum_combinations:
					two_sum_combinations[x + y] = set()
				two_sum_combinations[x + y].add((maxval, minval))
		for z in unique_values:
			if target - z in two_sum_combinations:
				for (x, y) in two_sum_combinations[target - z]:
					if z <= y:
						weight = self.calculate_weight(x, y, z, freq)
						print((x, y, z, weight))
						count += weight
		return count % (10 ** 9 + 7)


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:

		def find_n_sum(arr, target, N, l, r, path, output):
			if arr[l] * N > target or arr[r] * N < target:
				return
			if N == 2:
				(s, e) = (l, r)
				while s < e:
					total = arr[s] + arr[e]
					if total < target or (s > l and arr[s - 1] == arr[s]):
						s += 1
					elif total > target or (e < r and arr[e] == arr[e + 1]):
						e -= 1
					else:
						output.add(tuple(path + [arr[s], arr[e]]))
						s += 1
						e -= 1
			else:
				for i in range(l, r + 1 - (N - 1)):
					if i > l and arr[l] == arr[l - 1]:
						continue
					find_n_sum(arr, target - arr[i], N - 1, i, r, path + [arr[i]], output)
		combos = set()
		res = 0
		counter = Counter(A)
		new_arr = []
		for k in sorted(counter.keys()):
			new_arr += [k] * min(counter[k], 3)
		find_n_sum(new_arr, target, 3, 0, len(new_arr) - 1, [], combos)
		for lst in combos:
			cnt = 1
			temp = Counter(lst)
			for k in temp:
				for i in range(temp[k]):
					cnt *= (counter[k] - i) / (i + 1)
			res = (res + cnt) % (10 ** 9 + 7)
		return int(res) % (10 ** 9 + 7)


from collections import Counter

class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		mp = Counter(A)
		total = 0
		mpow = 10 ** 9 + 7
		for i in range(101):
			for j in range(i, 101):
				calc = target - (i + j)
				if calc > 100 or calc < 0:
					continue
				if i == j == calc:
					x = mp[i]
					top_row = x * (x - 1) * (x - 2)
					top_row /= 6
					total += top_row
				elif i == j != calc:
					x = mp[i]
					total += x * (x - 1) / 2 * mp[calc]
				elif i < j < calc:
					total += mp[i] * mp[j] * mp[calc]
		return int(total % mpow)


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		from collections import Counter
		A.sort()
		c = Counter(A)
		res = 0
		pre = -1
		for i in range(len(A)):
			if A[i] == pre:
				continue
			pre = A[i]
			right = len(A) - 1
			left = i + 1
			while left < right:
				if A[i] + A[left] + A[right] < target:
					left += 1
				elif A[i] + A[left] + A[right] > target:
					right -= 1
				else:
					if A[i] == A[right]:
						num = c[A[i]] * (c[A[i]] - 1) * (c[A[i]] - 2) / 6
					elif A[i] == A[left]:
						num = c[A[i]] * (c[A[i]] - 1) / 2 * c[A[right]]
					elif A[left] == A[right]:
						num = c[A[left]] * (c[A[left]] - 1) / 2 * c[A[i]]
					else:
						num = c[A[i]] * c[A[left]] * c[A[right]]
					res += num
					tmp_pre = A[left]
					while left < right and A[left] == tmp_pre:
						left += 1
					tmp_pre = A[right]
					while left < right and A[right] == tmp_pre:
						right -= 1
		return int(res) % (10 ** 9 + 7)


class Solution:

	def threeSumMulti(self, A, target: int) -> int:
		M = 1000000007
		record = {}
		for i in A:
			if i in record.keys():
				record[i] = record[i] + 1
			else:
				record[i] = 1
		k_list = list(record.keys())
		k_list.sort()
		n = len(k_list)
		res = 0
		for i in range(n):
			for j in range(i, n):
				residual = target - k_list[i] - k_list[j]
				if residual < k_list[j]:
					continue
				if i == j:
					if record[k_list[i]] == 1:
						continue
					elif residual in record.keys():
						if residual == k_list[j]:
							res = res + int(record[k_list[i]] * (record[k_list[i]] - 1) * (record[k_list[i]] - 2) / 6)
							res = res % M
						else:
							multi = record[residual]
							res = res + int(record[k_list[i]] * (record[k_list[i]] - 1) / 2 * multi)
							res = res % M
					else:
						continue
				elif residual in record.keys():
					if residual == k_list[j]:
						res = res + int(record[k_list[i]] * record[k_list[j]] * (record[k_list[j]] - 1) / 2)
						res = res % M
					else:
						multi = record[residual]
						res = res + int(record[k_list[i]] * record[k_list[j]] * multi)
						res = res % M
				else:
					continue
		return res


from collections import Counter, defaultdict

class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		A.sort()
		dic = defaultdict(list)
		count = Counter(A)
		B = list(count.keys()) * 3
		B.sort()
		seen = set()
		ans = 0
		for i in range(len(B)):
			dic[B[i]].append(i)
		for i in range(len(B) - 2):
			for j in range(i + 1, len(B) - 1):
				temp = target - B[i] - B[j]
				if temp in dic:
					k = dic[temp][-1]
					if k > j:
						seen.add((B[i], B[j], B[k]))

		def comb(n, m):
			N = list(range(n - m + 1, n + 1))
			M = list(range(1, m + 1))
			nn = 1
			mm = 1
			for i in N:
				nn *= i
			for i in M:
				mm *= i
			return int(nn / mm)
		for t in seen:
			temp = 1
			c = Counter(t)
			print(t)
			for i in c:
				m = c[i]
				n = count[i]
				if m > n:
					temp = 0
					break
				temp *= comb(n, m)
			ans += temp
		return ans % (10 ** 9 + 7)


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		A.sort()
		leftDict = defaultdict(int)
		rightDict = Counter(A[1:])
		ALen = len(A)
		MOD = 10 ** 9 + 7
		leftDict[A[0]] += 1
		ans = 0
		for i in range(1, ALen - 1):
			Ai = A[i]
			rightDict[Ai] -= 1
			for left in leftDict:
				ans += leftDict[left] * rightDict[target - Ai - left]
			leftDict[Ai] += 1
			ans %= MOD
		return ans


from collections import defaultdict

class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		single = defaultdict(int)
		double = defaultdict(int)
		ans = 0
		for x in A:
			ans += double[target - x]
			for (k, v) in single.items():
				double[k + x] += v
			single[x] += 1
		return ans % (10 ** 9 + 7)


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		d1 = collections.defaultdict(int)
		d2 = collections.defaultdict(int)
		N = len(A)
		MOD = 10 ** 9 + 7
		cnt = 0
		for i in range(N - 1, -1, -1):
			n = A[i]
			cnt += d2[target - n]
			cnt %= MOD
			for (nn, nncnt) in list(d1.items()):
				d2[nn + n] += nncnt
			d1[n] += 1
		return cnt


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		d1 = collections.defaultdict(int)
		d2 = collections.defaultdict(int)
		ans = 0
		for i in A:
			ans += d2[target - i]
			for j in d1:
				d2[j + i] += d1[j]
			d1[i] += 1
		return ans % int(1000000000.0 + 7)


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		A.sort()
		N = len(A)
		ans = 0
		counts = self.get_counts(A)
		for i in range(N - 2):
			two_sum_target = target - A[i]
			counts[A[i]] -= 1
			ans += self.two_sum(A, i + 1, two_sum_target, counts)
		return ans % (10 ** 9 + 7)

	def two_sum(self, A, i, target, counts):
		j = len(A) - 1
		ans = 0
		while i < j:
			if A[i] + A[j] < target:
				i += counts[A[i]]
			elif A[i] + A[j] > target:
				j -= counts[A[j]]
			else:
				if A[i] == A[j]:
					v = counts[A[i]]
					ans += v * (v - 1) // 2
				else:
					v1 = counts[A[i]]
					v2 = counts[A[j]]
					ans += v1 * v2
				i += counts[A[i]]
				j -= counts[A[j]]
		return ans

	def get_counts(self, A):
		d = {}
		for num in A:
			if num not in d:
				d[num] = 0
			d[num] += 1
		return d


import math
import collections

class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		c1 = collections.Counter(A)
		arr = []
		triples = set()
		for i in sorted(c1.keys()):
			arr += [i] * min(3, c1[i])
		for i in range(len(arr) - 2):
			j = i + 1
			k = len(arr) - 1
			twoSum = target - arr[i]
			while j < k:
				tmp = arr[j] + arr[k]
				if tmp == twoSum:
					triples.add((arr[i], arr[j], arr[k]))
					k -= 1
				elif tmp >= twoSum:
					while k - 1 > 0 and arr[k - 1] == arr[k]:
						k -= 1
					k -= 1
				else:
					while j + 1 < len(arr) - 1 and arr[j + 1] == arr[j]:
						j += 1
					j += 1
		tot = 0
		mod = 10 ** 9 + 7
		for t in triples:
			c2 = collections.Counter(t)
			combs = 1
			for k in list(c2.keys()):
				combs *= math.comb(c1[k], c2[k])
				combs %= mod
			tot += combs
			tot %= mod
		return tot


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		c = collections.Counter(A)
		res = 0
		for (i, j) in itertools.combinations_with_replacement(c, 2):
			k = target - i - j
			if i == j == k:
				res += c[i] * (c[i] - 1) * (c[i] - 2) / 6
			elif i == j != k:
				res += c[i] * (c[i] - 1) / 2 * c[k]
			elif k > i and k > j:
				res += c[i] * c[j] * c[k]
		return int(res % (10 ** 9 + 7))


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		counter = [0] * 101
		for num in A:
			counter[num] += 1
		count = 0
		MOD = int(10 ** 9 + 7)
		for i in range(len(A) - 2):
			counter[A[i]] -= 1
			residual = target - A[i]
			for Aj in range(101):
				Ak = residual - Aj
				if Ak >= 0 and Ak <= 100 and (Aj <= Ak):
					if Aj != Ak:
						count += counter[Aj] * counter[Ak]
					else:
						count += counter[Aj] * (counter[Aj] - 1) // 2
		return count % MOD


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		res = 0
		mod = int(1000000000.0 + 7)
		numbers = dict()
		sums = dict()
		for num in A:
			res = (res + sums.get(target - num, 0)) % mod
			for (number, count) in list(numbers.items()):
				sums[number + num] = sums.get(number + num, 0) + count
			numbers[num] = numbers.get(num, 0) + 1
		return res


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		cnt1 = collections.Counter()
		cnt2 = collections.Counter()
		result = 0
		M = 10 ** 9 + 7
		for a in A:
			cnt2[a] += 1
		for a in A:
			cnt2[a] -= 1
			if cnt2[a] == 0:
				cnt2.pop(a)
			for (i, j) in cnt1.items():
				k = target - i - a
				result = (result + j * cnt2[k]) % M
			cnt1[a] += 1
		return result


from collections import Counter

class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		c = Counter(A)
		res = 0
		s = list(set(A))
		s.sort()
		trips = set()
		for i in range(len(s)):
			if i > target / 3:
				break
			n = s[i]
			l = i
			r = len(s) - 1
			while l <= r:
				a = s[i] + s[l] + s[r]
				if a == target:
					trips.add((s[i], s[l], s[r]))
					l += 1
					r -= 1
				elif a > target:
					r -= 1
				else:
					l += 1
		print(trips)
		for t in trips:
			a = 1
			for n in set(t):
				count = c[n]
				if t.count(n) == 3:
					a *= count * (count - 1) * (count - 2) / 6
				elif t.count(n) == 2:
					a *= count * (count - 1) / 2
				else:
					a *= count
			res += a
		return int(res) % (10 ** 9 + 7)


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		m = collections.Counter(A)
		res = 0
		for (n0, n1) in itertools.combinations_with_replacement(m, 2):
			n2 = target - n0 - n1
			if n0 == n1 == n2:
				res += m[n0] * (m[n0] - 1) * (m[n0] - 2) // 6
			elif n0 == n1 != n2:
				res += m[n0] * (m[n0] - 1) // 2 * m[n2]
			elif max(n0, n1) < n2:
				res += m[n0] * m[n1] * m[n2]
		return res % (10 ** 9 + 7)


class Solution:

	def threeSumMulti(self, A: List[int], target: int) -> int:
		MOD = 1000000007
		count = [0] * 101
		for x in A:
			count[x] += 1
		ans = 0
		for x in range(101):
			for y in range(x + 1, 101):
				z = target - x - y
				if y < z <= 100:
					ans += count[x] * count[y] * count[z]
					ans %= MOD
		for x in range(101):
			z = target - 2 * x
			if x < z <= 100:
				ans += count[x] * (count[x] - 1) // 2 * count[z]
				ans %= MOD
		for x in range(101):
			if (target - x) % 2 == 0:
				y = (target - x) // 2
				if x < y <= 100:
					ans += count[x] * count[y] * (count[y] - 1) // 2
					ans %= MOD
		if target % 3 == 0:
			x = target // 3
			if 0 <= x <= 100:
				ans += count[x] * (count[x] - 1) * (count[x] - 2) // 6
				ans %= MOD
		return ans


from math import comb

class Solution:

	def threeSumMulti(self, a: List[int], target: int) -> int:
		counts = Counter(a)
		ans = 0
		for i in list(counts.keys()):
			for j in list(counts.keys()):
				k = target - i - j
				if i == j == k:
					ans += comb(counts[i], 3)
				elif i == j and j < k:
					ans += comb(counts[i], 2) * counts[k]
				elif i < j and j == k:
					ans += counts[i] * comb(counts[k], 2)
				elif i < j < k:
					ans += counts[i] * counts[j] * counts[k]
		return ans % (10 ** 9 + 7)