题解

题目描述

给定一个由 $n$ 个正整数构成的数组 $\{a_1,a_2,\dots,a_n\}$，要求从中选择至多 $k$ 个数， 使得这些数的乘积恰好为 $p$ 的倍数。
输入时，第一行给出正整数 $n,k,p$（其中 $1\le n,p\le 100$ 且 $1\le k\le n$），代表数组的元素数量、最多可以挑选的元素个数以及倍数 $p$；第二行给出 $n$ 个正整数 $a_1,a_2,\dots,a_n$（每个 $a_i$ 满足 $1\le a_i\le 10^9$）。
输出时，将满足条件的选数方案总数对 $10^9+7$ 取模后输出。

题目内容

对于给定的由$n$个正整数构成的数组 {$a_1,a_2,…,a_n$} ,从中选择至多 $k$ 个数,使得这些数的乘积恰好为 $p$ 的倍数。

小美想知道，一共有多少种满足条件的选数方案？由于答案可能很大,请将答案对 $(10^9+7)$ 取模后输

输入描述

第一行输入三个正整数 $n,k,p(1≦n,p≦100;1≦k≦n)$ 代表数组中的元素数量、至多挑选的元素数量,位期的涨取用

第二方输入 $n$ 个正整数 $a_1，a_2,...,a_n(1≤a_i≤10^9)$ 代表教组中的元素。

输出描述

在一行上输出一个整数，代表满足条件的选数方案。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

样例1

输入

5 5 30
1 2 3 4 5

输出

6