题目内容

小蓝收藏了 $n$ 颗宝石，第 $i$ 颗宝石的魔力值为 $a_i$。他计划挑选不超过 $k$ 颗宝石，希望这些宝石的魔力值之积能够被幸运数字 $p$ 整除。请你计算他有多少种不同的挑选方案。由于答案可能很大，请将答案对 $10^9+7$ 取模后输出。

数据范围：宝石数量 $n$ 满足 $1 \le n \le 100$，幸运数字 $p$ 满足 $1 \le p \le 100$，最多挑选数量 $k$ 满足 $1 \le k \le n$。每颗宝石的魔力值 $a_i$ 满足 $1 \le a_i \le 10^9$。

输入描述

第一行包含三个整数 $n$，$k$，$p$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每颗宝石的魔力值。