1305C.md (1515B)
1 Source: https://codeforces.com/problemset/problem/1305/C 2 3 C. Kuroni and Impossible Calculation 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 To become the king of Codeforces, Kuroni has to solve the following problem. 22 23 He is given $n$ numbers $a_1, a_2, \dots, a_n$. Help Kuroni to calculate $\prod_{1\le i \lt j\le n} |a_i - a_j|$. As result can be very big, output it modulo $m$. 24 25 If you are not familiar with short notation, $\prod_{1\le i \lt 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 \lt j \le n$. 26 27 Input 28 29 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. 30 31 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$). 32 33 Output 34 35 Output the single number — $\prod_{1\le i \lt j\le n} |a_i - a_j| \bmod m$. 36 37 Examples 38 39 Input 40 41 ``` 42 2 10 43 8 5 44 ``` 45 46 Output 47 48 ``` 49 3 50 ``` 51 52 Input 53 54 ``` 55 3 12 56 1 4 5 57 ``` 58 59 Output 60 61 ``` 62 0 63 ``` 64 65 Input 66 67 ``` 68 3 7 69 1 4 9 70 ``` 71 72 Output 73 74 ``` 75 1 76 ``` 77 78 Note 79 80 In the first sample, $|8 - 5| = 3 \equiv 3 \bmod 10$. 81 82 In the second sample, $|1 - 4|\cdot|1 - 5|\cdot|4 - 5| = 3\cdot 4 \cdot 1 = 12 \equiv 0 \bmod 12$. 83 84 In the third sample, $|1 - 4|\cdot|1 - 9|\cdot|4 - 9| = 3 \cdot 8 \cdot 5 = 120 \equiv 1 \bmod 7$.