Autumn Cleaning (16 MiB ML!)

Autumn is coming, and Sophie wants to prepare for it by emptying her grandparents' basement. She wants to sell unused items, so she put a price tag on each of them (non-negotiable!) and posted the offer online. Some items may have the same price. A junk dealer contacted her quickly, and he wants to buy exactly $k$ items, no matter which ones (junk is junk). Unfortunately, he visited the ATM only a moment ago, so he has only a lot of $r$-zloty bills ('zloty' is the Polish currency). In how many different ways can they make a trade?

The first line of the input contains three positive integers $n, k$ and $r$ ($1\leq n \leq 10^6$, $1\leq k \leq 3\,000$, $1\leq r \leq 10$), denoting the number of items Sophie wants to sell, the number of items the junk dealer wants to buy, and the face value of the bills he has. The second and last line of the input contains $n$ positive integers $a\_i$ ($1 \le a\_i \le 10^6$). These are the prices of the items Sophie wants to sell.

Print a single positive integer: the remainder modulo $10^6+3$ of the number of sets of $k$ items whose total price is divisible by $r$.

The junk dealer can buy the first, second and fifth items, with a total price of $8+1+3 = 12$, or the first, third and fourth items, paying $8+2+2=12$.