秋天快到了，Sophie 想要通过清理她祖父母的地下室来做准备。她想卖掉一些闲置物品，并且已经给所有物品贴上了价格标签（谢绝还价！），还将这些商品发布到了网上。请注意，某些物品的价格可能相同。

很快，一位收废品的商人联系了她，他想恰好购买 $k$ 件物品，买什么都无所谓（反正都是废品）。不幸的是，他刚刚去过自动取款机，身上只有许多面额为 $r$ 兹罗提（zloty，波兰货币单位）的纸币。

他们有多少种不同的方式来进行这笔交易（即选择 $k$ 件物品，使得它们的总价可以被 $r$ 整除，从而可以用 $r$ 兹罗提的纸币正好付清，不需要找零）？

输入格式

输入的第一行包含三个正整数 $n, k$ 和 $r$（$1 \le n \le 10^6$，$1 \le k \le 3000$，$1 \le r \le 10$），分别表示：Sophie 想要出售的物品数量、废品商人想要购买的物品数量，以及他拥有的纸币面额。

输入的第二行（也是最后一行）包含 $n$ 个正整数 $a_i$（$1 \le a_i \le 10^6$），表示 Sophie 想要出售的物品的价格。

输出格式

输出一个正整数：总价能被 $r$ 整除的 $k$ 件物品的组合数模 $10^6 + 3$ 的余数。

样例

输入样例 1

5 3 4
8 1 2 2 3

输出样例 1

2

说明

废品商人可以购买第一、第二和第五件物品，总价为 $8 + 1 + 3 = 12$；或者购买第一、第三和第四件物品，支付 $8 + 2 + 2 = 12$。