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: interview

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

        # Now, let's do a 3sum on \"keys\", for i <= j <= k.
        # We will use count to add the correct contribution to ans.
        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: # x+y+z == T, now calculate the size of the contribution
                    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:  # i == j == k
                        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 #C x 3
                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

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()))
        print(counter)
        print((l//2))
        if target % 3 == 0:
            res += math.comb(counter[target // 3], 3)
            print((target//3, target//3, target//3, res))
        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]
            print((ni, ni, nk, res))
        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]
                print((ni, nj, nk, res))
        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(object):
    def threeSumMulti(self, A, target):
        MOD = 10**9 + 7
        count = collections.Counter(A)
        keys = sorted(count)

        ans = 0

        # Now, let's do a 3sum on \"keys\", for i <= j <= k.
        # We will use count to add the correct contribution to ans.
        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: # x+y+z == T, now calculate the size of the contribution
                    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:  # i == j == k
                        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6

                    j += 1
                    k -= 1

        return int(ans % MOD)

from collections import Counter

class Solution:
    def threeSumMulti(self, A: List[int], target: int) -> int:
        countA = Counter(A)
        ans = 0
        done = set()
        M = int(1e9 + 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
        # check all same:
        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))
        # 2 are same:
        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))
        # all distinct
        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))
        
        
#         for i in range(len(keys)):
#             if keys[i] > target:
#                  return totWays
                
#             if ADict[keys[i]] ==1:
#                 startJ = i+1
#             else:
#                 startJ = i
#                 ijSame = True
#             for j in range(startJ, len(keys)):
#                 sum = keys[i] + keys[j]
#                 if sum > target:
#                      break
#                 remaining = target - sum
#                 if remaining in keys:
#                      totWays+=1
#         #             tempA.remove(remaining)
                
            
        #for ele in ADict.keys():
            
        
        
        # A = sorted(A)
        # #print(A)
        # if len(A)<3:
        #     return 0
        # totWays = 0
        # for i in range (len(A)):
        #     if A[i] >target:
        #         return totWays
        #     for j in range (i+1, len(A)):
        #         tempA = A[j+1:].copy()
        #         sum = A[i] + A[j]
        #         if sum > target:
        #             break
        #         remaining = target - sum
        #         while remaining in tempA:
        #             totWays+=1
        #             tempA.remove(remaining)
        #             #print (str(A[i]) + \" \" + str(A[j]) + \" \" + str(remaining))
        # return totWays


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 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 = {}
        print((len(A)))
        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 int(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#nC3
                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)
        

#     def threeSumMulti(self, A: List[int], target: int) -> int:
#         total = 0
#         A.sort()
#         mod_pow = 10**9 + 7
#         for i in range(len(A)):
#             l = i+1
#             r = len(A)-1
#             while l < r:
#                 calc = A[i] + A[l] + A[r]
#                 if calc > target:
#                     r -= 1
#                 elif calc < target:
#                     l += 1
#                 elif A[l] == A[r]:
#                     x = r-l+1
#                     comb = (x*(x-1)) / 2
#                     total += comb
#                     break
#                 else:
#                     lcount = 1
#                     rcount = 1
#                     while l+1 < r and A[l] == A[l+1]:
#                         lcount += 1
#                         l += 1
#                     while r-1 > l and A[r] == A[r-1]:
#                         rcount += 1
#                         r -= 1
#                     total += (lcount*rcount)
#                     l += 1
#                     r -= 1                    
                
#         return int(total%mod_pow)


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()
        #print(k_list)
        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
                    else:
                        if(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
                        
                        #print(k_list[i], record[k_list[i]], multi)
                else:
                    if(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
                    
                    #print(k_list[i], k_list[j], record[k_list[i]], record[k_list[j]], multi)
        
        return res

# from collections import Counter

# class Solution(object):
#     def threeSumMulti(self, A, target):
#         MOD = 10**9 + 7
#         count = [0] * 101
#         for x in A:
#             count[x] += 1

#         ans = 0

#         # All different
#         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

#         # x == y
#         for x in range(101):
#             z = target - 2*x
#             if x < z <= 100:
#                 ans += count[x] * (count[x] - 1) / 2 * count[z]
#                 ans %= MOD

#         # y == z
#         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

#         # x == y == z
#         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 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)


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(1e9 + 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 d1.items():
                d2[nn+n]+=nncnt

            d1[n]+=1

        return cnt 

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


# class Solution:
#     def threeSumMulti(self, A: List[int], target: int) -> int:
#         # 1 enumerating
#         # 2. backtracking
#         if len(A)<3:
#             return 0
        
#         A.sort()
#         self.target = target
#         self.backtrace(A, [])
#         #print(A,self.target, self.allPaths)
#         return len(self.allPaths)
    
#     def __init__(self):
#         self.allPaths = []
    
#     def backtrace(self, nums, path):
#         if len(path) == 3:
#             if sum(path)==self.target:
#                 self.allPaths.append(path)
#             return
# #         if len(path) > 3:
# #             return
#         #print(len(nums), path)
#         for i in range(len(nums)):
#             if sum(path) <= self.target:
#                 uPath = path + [nums[i]]
#                 #print(uPath)
#                 # allocate remaining
#                 uNums = nums[i+1:]
#                 self.backtrace(uNums, uPath)
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])
            
        # find candidates from arr
        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
        # count the combinations
        tot = 0
        mod = 10**9 + 7
        #print(triples)
        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
                    #print(A[i], Aj, Ak, count)
        return count % MOD

class Solution:
    def threeSumMulti(self, A: List[int], target: int) -> int:
        # hashtable with dp
        
        res = 0
        mod = int(1e9+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]
            # print((n0, n1, n2), 'res', res)
            
        return res % (10**9 + 7)
                
        
        
        
        
        
        
#         m = collections.Counter(A)
#         keys = sorted(m.keys())
#         def twoSums(left, target):
#             res = 0
#             for i in range(left, len(keys)):
#                 n = keys[i]
#                 if n * 2 > target:
#                     break
#                 if n * 2 == target:
#                     res += m[n] * (m[n] - 1) // 2
#                     break
#                 res += m[n] * m[target - n]
#             return res
        
#         res = 0
#         for i, n in enumerate(keys):
#             if n * 3 > target:
#                 break
#             if n * 3 == target:
#                 res += m[n] * (m[n] - 1) * (m[n] - 2) // 6
#                 break
            
#             res += (m[n] * (m[n] - 1) // 2) * m[target - n * 2]
#             count, m[n] = m[n], 0
#             res += count * twoSums(i + 1, target - n)
#         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)