codeforces 1305 C. Kuroni and Impossible Calculation（抽屉原理）

C. Kuroni and Impossible Calculation

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

由抽屉原理知，当n > m时，一定存在两个 ai 模 m 同余，答案是0

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;

int a[N];

int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
        }
        if(n > m)
        {
            cout<<0<<'\n';
            continue;
        }
        ll ans = 1;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = i + 1; j <= n; ++j)
            {
                ans = ans % m * abs(a[i] - a[j]) % m;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}