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

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

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

Input
The first line contains two integers n, m (2≤n≤2?105, 1≤m≤1000) — number of numbers and modulo.

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

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

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≡3mod10.

In the second sample, |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.
思路：鴿巢原理真的很神奇，有的時(shí)候很麻煩的一件事突然就很明朗了。
如果n>m,那么一定有兩個(gè)數(shù)字取余m相等，那么他們相減之后就肯定為0，最終結(jié)果也為0.這樣就只暴力考慮1000之內(nèi)的情況就可以了。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=2e5+100; int a[maxx]; int n,m;int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) cin>>a[i];//for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;if(n>m) cout<<0<<endl;else{ll ans=1ll;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++) ans=(ans*(ll)abs(a[i]-a[j]))%m;}cout<<ans%m<<endl;//for(m=1;m<=1000;m++) cout<<ans%m<<endl;}return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的Kuroni and Impossible Calculation CodeForces - 1305C（鸽巢原理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。