가을 대청소 (16 MiB ML!)

가을이 다가오자 Sophie는 조부모님의 지하실을 비우려 한다. 쓰지 않는 물건을 팔려고 모든 물건에 가격표를 붙였고(가격은 흥정 불가!), 그 판매 제안을 인터넷에 올렸다. 같은 가격인 물건이 있을 수도 있다. 곧 고물상이 연락해 왔는데, 그는 어떤 물건이든 상관없이 정확히 $k$개의 물건을 사려 한다(고물은 고물이니까). 그런데 그는 방금 전에 현금인출기를 다녀왔고, $r$ 즐로티짜리 지폐만 잔뜩 가지고 있다('즐로티'는 폴란드 화폐이다). 두 사람이 거래를 성사시킬 수 있는 서로 다른 방법은 몇 가지인가?

입력의 첫째 줄에 세 양의 정수 $n, k, r$이 주어진다($1\leq n \leq 10^6$, $1\leq k \leq 3\,000$, $1\leq r \leq 10$). 각각 Sophie가 팔려는 물건의 개수, 고물상이 사려는 물건의 개수, 그가 가진 지폐의 액면가이다. 입력의 둘째 줄이자 마지막 줄에 $n$개의 양의 정수 $a\_i$가 주어진다($1 \le a\_i \le 10^6$). 이는 Sophie가 팔려는 물건의 가격이다.

총가격이 $r$로 나누어떨어지는 $k$개 물건의 집합의 개수를 $10^6+3$으로 나눈 나머지를 하나의 양의 정수로 출력한다.

고물상은 첫째, 둘째, 다섯째 물건을 사서 총가격 $8+1+3 = 12$를 지불하거나, 첫째, 셋째, 넷째 물건을 사서 $8+2+2=12$를 지불할 수 있다.