In this problem you are given a sequence of $N$ positive integers $S[1],S[2],\dots,S[N]$. In addition you are given an integer $T$, and your aim  is to find the number of quadruples $(i,j,k,l)$, such that $1 \le i < j < k < l \le N$, and $S[i] + S[j] + S[k] + S[l] = T$.  That is, the number of ways of picking four numbers from the sequence summing up to $T$.

-----Constraints:-----
For all test cases,
- $1 \le N \le 5000$
- $1 \le T \le 10^6$
- $1 \le S[i] \le 10^9$, for all $i$.
Subtask $1:10\%$
It is guaranteed that $N \le 50$.
Subtask $2:50\%$
It is guaranteed that $N \le 300$.
Subtask $3:40\%$
No additional guarantees.

-----Input Format:-----
There is only one line of input with $N+2$ space separated integers. The first two integers are $N$ and $T$. The next $N$ integers are $S[1],S[2],\dots,S[N]$.

-----Output Format:-----
A single integer which is the number of valid quadruples.

-----Sample Input 1:-----
6 20 3 1 1 2 5 10

-----Sample Output 1:-----
1

-----Explanation 1:-----
The quadruple $(1,4,5,6)$ is valid  because $S[1]+S[4]+S[5]+S[6]=3+2+5+10=20$. You can check that no other quadruple is valid and hence the answer is $1$.

-----Sample Input 2:-----
6 13 1 2 3 4 5 4 

-----Sample Output 2:-----
3

-----Explanation 2:-----
You can verify that the only quadruples that are valid are $(2,3,4,6),(1,3,4,5)$  and $(1,3,5,6)$. Thus, the answer is $3$.

-----Note:-----
As the answer might be large, please use 64 bit integers (long long int in
C/C++ and long in Java) instead of 32 bit int.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "# cook your dish here\n'''\nfrom operator import itemgetter\ninp=list(map(int, input().split()))\nn, t = inp[0], inp[1]\narray=inp[2:]\narray.sort()\nfreq={}\nfor el in array:\n    if el not in freq:\n        freq[el]=1 \n    else:\n        freq[el]+=1\nsomme=[]\nfor i in range(n-1):\n    for j in range(i+1,n):\n        somme.append((array[i]+array[j], {i, j}))\nsomme.sort(key=itemgetter(0))\ni_end=len(somme)-1\ncounter=0\ncomputed={}\nfor i in range(len(somme)-1):\n    while i_end>i and somme[i][0]+somme[i_end][0]>t:\n        i_end-=1\n    if i_end==i:\n        break\n    if somme[i][0]+somme[i_end][0]==t and len(somme[i][1]&somme[i_end][1])==0:\n        id_start, i_mid1, i_mid2, id_end = sorted(somme[i][1]|somme[i_end][1])\n        if (array[id_start], array[i_mid1], array[i_mid2], array[id_end]) not in computed:\n            if array[id_start]==array[id_end]:\n                appo=freq[array[id_start]]\n                counter+=appo*(appo-1)*(appo-2)*(appo-3)//24\n            elif array[id_start]==array[i_mid2]:\n                appo=freq[array[i_mid1]]\n                counter+=appo*(appo-1)*(appo-2)*freq[array[id_end]]//6\n            elif array[id_end]==array[i_mid1]:\n                appo=freq[array[i_mid1]]\n                counter+=appo*(appo-1)*(appo-2)*freq[array[id_start]]//6\n            elif array[id_start]==array[i_mid1] and array[id_end]==array[i_mid2]:\n                counter+=freq[array[i_mid1]]*(freq[array[i_mid1]]-1)*freq[array[i_mid2]]*(freq[array[i_mid2]]-1)//4\n            elif array[id_start]==array[i_mid1]:\n                counter+=freq[array[i_mid1]]*(freq[array[i_mid1]]-1)*freq[array[i_mid2]]*freq[array[id_end]]//2\n            elif array[id_end]==array[i_mid2]:\n                counter+=freq[array[i_mid2]]*(freq[array[i_mid2]]-1)*freq[array[i_mid1]]*freq[array[id_start]]//2\n            else:\n                counter+=freq[array[id_start]]*freq[array[id_end]]*freq[array[i_mid1]]*freq[array[i_mid2]]\n            computed[(array[id_start], array[i_mid1], array[i_mid2], array[id_end])]=1\nprint(counter)\n\narray.sort()\nfreq={}\nfor el in array:\n    if el not in freq:\n        freq[el]=1 \n    else:\n        freq[el]+=1\ncounter=0\nid_start=0\nid_end=n-1\ncomputed={}\nfor id_start in range(n-3):\n    while id_end>id_start+2 and t-array[id_start]-array[id_end]<array[id_start+1]+array[id_start+2]:\n        id_end-=1\n    if id_end==id_start+2:\n        break\n    t_new=t-array[id_start]-array[id_end]\n    i_mid2=id_end-1\n    for i_mid1 in range(id_start+1, id_end-1):\n        print(array[id_start], array[i_mid1], array[i_mid2], array[id_end])\n        while i_mid2>i_mid1 and array[i_mid1]+array[i_mid2]>t_new:\n            i_mid2-=1 \n        if i_mid2==i_mid1:\n            break\n        if array[i_mid1]+array[i_mid2]==t_new and (array[id_start], array[i_mid1], array[i_mid2], array[id_end]) not in computed:\n            if array[id_start]==array[id_end]:\n                appo=freq[array[id_start]]\n                counter+=appo*(appo-1)*(appo-2)*(appo-3)//24\n            elif array[id_start]==array[i_mid2]:\n                appo=freq[array[i_mid1]]\n                counter+=appo*(appo-1)*(appo-2)*freq[array[id_end]]//6\n            elif array[id_end]==array[i_mid1]:\n                appo=freq[array[i_mid1]]\n                counter+=appo*(appo-1)*(appo-2)*freq[array[id_start]]//6\n            elif array[id_start]==array[i_mid1] and array[id_end]==array[i_mid2]:\n                counter+=freq[array[i_mid1]]*(freq[array[i_mid1]]-1)*freq[array[i_mid2]]*(freq[array[i_mid2]]-1)//4\n            elif array[id_start]==array[i_mid1]:\n                counter+=freq[array[i_mid1]]*(freq[array[i_mid1]]-1)*freq[array[i_mid2]]*freq[array[id_end]]//2\n            elif array[id_end]==array[i_mid2]:\n                counter+=freq[array[i_mid2]]*(freq[array[i_mid2]]-1)*freq[array[i_mid1]]*freq[array[id_start]]//2\n            else:\n                counter+=freq[array[id_start]]*freq[array[id_end]]*freq[array[i_mid1]]*freq[array[i_mid2]]\n            computed[(array[id_start], array[i_mid1], array[i_mid2], array[id_end])]=1\nprint(counter)\n'''\n\nnums = list(map(int, input().split()))\nn, t = nums.pop(0), nums.pop(0)\nways = [1] + [0]*t\nnums.sort()\nans = 0\nfor i in range(2, n):\n    if nums[i] > t - 3:\n        break\n    j = i-1\n    for k in range(0, j):\n        if nums[k] + nums[j] > t-2:\n            break\n        ways[nums[k] + nums[j]] += 1\n    for last in range(i+1, n):\n        if nums[i] + nums[last] > t - 2:\n            break\n        left = t - nums[i] - nums[last]\n        if left > 1:\n            ans += ways[left]\nprint(ans)"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13381