B. Xor or floor ?
time limit per test
0.3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
A fost odată ca-n poveşti,

A fost ca niciodată.

Din rude mari împărăteşti,

O prea frumoasă fată.

Şi era una la părinţi

Şi mândră-n toate cele,

Cum e Fecioara între sfinţi

Şi luna între stele.

— Mihai Eminescu , Luceafărul

After solving "Traveling salesman" problem in $$$O(E+V)$$$, multiplying polynomials in $$$O(N)$$$, proving the Collatz conjecture, understanding physics and finding a quadratic algorithm for multiplying matricies, $$$K0Kalaru47$$$ challanges you with this problem, in exchange for a chance of winning this $$$InfOleague™$$$ contest.

You are given an array $$$A$$$ of $$$N$$$ values smaller than $$$M$$$. The cost of a subset is the minimum $$$xor$$$ across all pairs in the subset. More formally, the cost of a set $$$B= {B_1,B_2,...,B_k}$$$ is equal to $$$min_{i \neq j \in [1,k]} (B_i \oplus B_j)$$$, where $$$\oplus$$$ denotes the bitwise xor operation. Find the sum of costs across all possible subsets of length greater than $$$1$$$ modulo $$$MOD$$$.

Input

The input consists of integers $$$N,M,MOD$$$ followed by an array $$$A$$$ of length $$$N$$$ with values in range $$$[0,M]$$$.

Output

Print one integer: The sum of costs across all subsets of length greater than $$$1$$$.

Scoring
  • For all test data , $$$N \cdot M \le 10^6$$$ , $$$2 \le MOD \le 10^9$$$
  • For 30 points , $$$N,M \le 100$$$
  • For the remaining $$$70$$$ points, there are no further restrictions
  • Note that $$$MOD$$$ may not be a prime number !
Examples
Input
3 5 666013
4 2 5
Output
15
Input
12 100 66013
32 69 39 51 49 30 51 32 0 0 0 100
Output
16807
Note

In the first sample , all the possible subsets are :

  • $$$[1,2,3]$$$ with cost $$$min(a[1] \oplus a[3],a[2] \oplus a[3],a[1] \oplus a[3])$$$ = 1
  • $$$[1,2]$$$ with cost $$$min(a[1] \oplus a[2]) = 6$$$
  • $$$[2,3]$$$ with cost $$$min(a[1] \oplus a[3]) = 1$$$
  • $$$[1,3]$$$ with cost $$$min(a[2] \oplus a[3]) = 7$$$

Therefore, the final answer is $$$1+6+1+7 = 15$$$