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

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

If you are not familiar with short notation, ∏_{1≤ i<j≤ n} |a_i - a_j| is equal to |a_1 - a_2|⋅|a_1 - a_3|⋅ ... ⋅|a_1 - a_n|⋅|a_2 - a_3|⋅|a_2 - a_4|⋅ ... ⋅|a_2 - a_n| ⋅ ... ⋅ |a_{n-1} - a_n|. In other words, this is the product of |a_i - a_j| for all 1≤ i < j ≤ n.

Input

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

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9).

Output

Output the single number — ∏_{1≤ i<j≤ n} |a_i - a_j| mod 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 ≡ 3 mod 10.

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

In the third sample, |1 - 4|⋅|1 - 9|⋅|4 - 9| = 3 ⋅ 8 ⋅ 5 = 120 ≡ 1 mod 7.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class KuroniandImpossibleCalculation {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");
        long n = Long.parseLong(s[0]);
        long m = Long.parseLong(s[1]);

        s = br.readLine().split(" ");
        long[] a = new long[(int) n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(s[i]);
        }

        long mul = 1;
        Arrays.sort(a);
        if (n > m) {
            System.out.println(0);
        } else {
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    mul = (int) (((long) mul * Math.abs(a[i] - a[j])) % m);
                }
            }
            System.out.println(mul);
        }
    }
}

/*import java.util.Scanner;
import java.util.Arrays;
public class Main
{
	public static void main(String[] args) {
		 Scanner s = new Scanner(System.in);
	    int n = s.nextInt();
	    int m = s.nextInt();
	    int mul=1;
	    int a[] = new int[n];
	    for(int i=0;i<n;i++)
	    {
	        a[i] = s.nextInt();
	    }
	    Arrays.sort(a);
	    if(n>m)
	    {
	        System.out.println(0);
	    }
	    else{
	    for(int i=0;i<n;i++)
	    {
	        for(int j=i+1;j<n;j++)
	        {
	            mul=(int)(((long)mul*Math.abs(a[i]-a[j]))%m);
	        }
	    }

	    System.out.println(mul);
         }
	}
}*/