链接:https://codeforces.ml/contest/1305/problem/C

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

He is given nn numbers a1,a2,…,ana1,a2,…,an. Help Kuroni to calculate ∏1≤i<j≤n|ai−aj|∏1≤i<j≤n|ai−aj|. As result can be very big, output it modulo mm.

If you are not familiar with short notation, ∏1≤i<j≤n|ai−aj|∏1≤i<j≤n|ai−aj| is equal to |a1−a2|⋅|a1−a3|⋅|a1−a2|⋅|a1−a3|⋅ …… ⋅|a1−an|⋅|a2−a3|⋅|a2−a4|⋅⋅|a1−an|⋅|a2−a3|⋅|a2−a4|⋅ …… ⋅|a2−an|⋅⋅|a2−an|⋅ …… ⋅|an−1−an|⋅|an−1−an|. In other words, this is the product of |ai−aj||ai−aj| for all 1≤i<j≤n1≤i<j≤n.

Input

The first line contains two integers nn, mm (2≤n≤2⋅1052≤n≤2⋅105, 1≤m≤10001≤m≤1000) — number of numbers and modulo.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤1090≤ai≤109).

Output

Output the single number — ∏1≤i<j≤n|ai−aj|modm∏1≤i<j≤n|ai−aj|modm.

Examples

input

Copy

2 10
8 5

output

Copy

3

input

Copy

3 12
1 4 5

output

Copy

0

input

Copy

3 7
1 4 9

output

Copy

1

Note

In the first sample, |8−5|=3≡3mod10|8−5|=3≡3mod10.

In the second sample, |1−4|⋅|1−5|⋅|4−5|=3⋅4⋅1=12≡0mod12|1−4|⋅|1−5|⋅|4−5|=3⋅4⋅1=12≡0mod12.

In the third sample, |1−4|⋅|1−9|⋅|4−9|=3⋅8⋅5=120≡1mod7|1−4|⋅|1−9|⋅|4−9|=3⋅8⋅5=120≡1mod7.

代码:

#include<bits/stdc++.h>
using namespace std;
long long n,m,t,s1,s2,s;
long long a[200001];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
    }
    if(n<=m)
    {
    	s=1;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=i+1;j<=n;j++)
    		{
    			s*=abs(a[i]-a[j])%m;
    			s%=m;
    		}
    	}
    	cout<<s<<endl;
    }
    else
    cout<<0<<endl;
}