B. Floor or xor ?
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
He can call me a flower if he wants to...

I don't mind...

— Redactia, Flower

You are given an array $$$A$$$ of $$$N$$$ numbers and an integer $$$T$$$. Find the number of tuples of indices $$$(i,j,k,l)$$$ such that $$$\lfloor \frac{A_i}{A_j} \rfloor + \lfloor \frac{A_k}{A_l} \rfloor$$$ = $$$T$$$.

Two tuples are $$$A$$$ and $$$B$$$ are distinct if there exists some $$$i$$$ such that $$$A_i \neq B_i$$$. For example , (1,1,2,4) is not the same as (1,2,1,4). Note that there may be repetitions.

Print the answer modulo $$$MOD$$$.

Input

The input consists of $$$N$$$,$$$T$$$ and $$$MOD$$$ followed by an array $$$A$$$ of size $$$N$$$.

Output

Print one integer : The number of tuples modulo $$$MOD$$$.

Scoring
  • $$$N \le 10^5$$$ , $$$1 \le A_i \le 5 \cdot 10^5$$$, $$$T \le 5 \cdot 10^5$$$, $$$MOD \le 10^9$$$.
  • For test data worth $$$20$$$ points , $$$N \le 50$$$ , $$$1 \le A_i \le 10^5$$$.
  • For another $$$20$$$ points, $$$N \le 2000$$$, $$$1 \le A_i \le 10^5$$$.
  • For another $$$30$$$ points, $$$1 \le A_i \le 10^5$$$
  • For the remaining $$$30$$$ points , there are no further restrictions.
Examples
Input
3 2 666013
1 1 1
Output
81
Input
10 2 9821672
372960 389034 286291 199826 189342 219065 129531 340535 69643 177416
Output
2410
Note

In the first sample it is easy to see that every possible tuple is good since $$$\lfloor \frac{1}{1} \rfloor + \lfloor \frac{1}{1} \rfloor = 2$$$. Thus print $$$3^4$$$ mod $$$666013 = 81$$$.

The second sample has a beautiful explination , but unfortunately it is too long to write.