To become the king of Codeforces, Kuroni has to solve the following problem.

He is given $n$ numbers $a_1, a_2, \dots, a_n$. Help Kuroni to calculate $\prod_{1\le i<j\le n} |a_i - a_j|$. As result can be very big, output it modulo $m$.

If you are not familiar with short notation, $\prod_{1\le i<j\le n} |a_i - a_j|$ is equal to $|a_1 - a_2|\cdot|a_1 - a_3|\cdot$ $\dots$ $\cdot|a_1 - a_n|\cdot|a_2 - a_3|\cdot|a_2 - a_4|\cdot$ $\dots$ $\cdot|a_2 - a_n| \cdot$ $\dots$ $\cdot |a_{n-1} - a_n|$. In other words, this is the product of $|a_i - a_j|$ for all $1\le i < j \le n$.


-----Input-----

The first line contains two integers $n$, $m$ ($2\le n \le 2\cdot 10^5$, $1\le m \le 1000$) — number of numbers and modulo.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$).


-----Output-----

Output the single number — $\prod_{1\le i<j\le n} |a_i - a_j| \bmod m$.


-----Examples-----
Input
2 10
8 5

Output
3
Input
3 12
1 4 5

Output
0
Input
3 7
1 4 9

Output
1


-----Note-----

In the first sample, $|8 - 5| = 3 \equiv 3 \bmod 10$.

In the second sample, $|1 - 4|\cdot|1 - 5|\cdot|4 - 5| = 3\cdot 4 \cdot 1 = 12 \equiv 0 \bmod 12$.

In the third sample, $|1 - 4|\cdot|1 - 9|\cdot|4 - 9| = 3 \cdot 8 \cdot 5 = 120 \equiv 1 \bmod 7$.

Difficulty: interview

Starter code:

Solutions:
from sys import stdin
input = stdin.readline
n,m = map(int,input().split())
l = list(map(int,input().split()))
if n > m:
	print(0)
else:
	res = 1
	for i in range(n-1):
		for j in range(i+1,n):
			res = ((res*abs(l[i]-l[j])) % m)
	print(res%m)

n,m = list(map(int,input().split()))
l=list(map(int,input().split()))
if n>m:
    print(0)
else:
    r=1
    for i in range(n):
        for s in range(i+1,n):
            r=r*abs(l[i]-l[s])
            r=r%m
    print(r)


N, M = list(map(int, input().split()))
A = sorted([int(a) for a in input().split()])

if N > M:
    print(0)
else:
    s = 1
    for i in range(N):
        for j in range(i):
            s = s * (A[i] - A[j]) % M
    print(s)


from itertools import combinations
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [a[i]%m for i in range(n)]
if len(set(b)) < n:
  print(0)
  return
ans = 1
for i,j in combinations(a,2):
  ans = (ans*abs(i-j))%m
print(ans)

from collections import deque
import sys
input = sys.stdin.readline

n, MOD = list(map(int, input().split()))
a = list(map(int, input().split()))
if n > MOD:
    print(0)
    return

ans = 1
for i in range(n):
    for j in range(i + 1, n):
        ans *= abs(a[i] - a[j])
        ans %= MOD
print(ans)