题目内容

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

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

题解

题目描述

给定一个由 $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$ 取模后输出。