An interesting counting problem about product division

Điểm: 2000 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 64M

Input: bàn phím

Output: màn hình

Tác giả:

huyhau6a2

Dạng bài

Một bài toán rất thú vị về tích chia hết

Bạn được cho dãy số $a$ gồm $n$ số và 2 số $m, k$ . Nhiệm vụ của bạn là đếm số bộ $k$ số $b_1,b_2,\dots,b_k$ ( $1\le b_1<b_2<\dots<b_k\le n$ ) thỏa mãn $a_{b_1}\times a_{b_2}\times \dots \times a_{b_k}$ chia hết cho $m$ . Vì kết quả có thể rất lớn nên hãy xuất kết quả sau khi $mod\ 10^9+7$

Input, Output và Subtasks

Input

Dòng đầu tiên chứa 3 số nguyên $n,m$ và $k$ ( $1\le k\le n\le 10^6,1\le m\le 10^9,k\le 10$ )
Dòng thứ hai chứa $n$ số nguyên không âm $a_1,a_2,\dots,a_n$ ( $0\le a_i\le 10^9$ )

Output

Số nguyên duy nhất là số bộ $k$ số thỏa mãn yêu cầu sau khi $mod\ 10^9+7$

Subtasks

Bài toán có 20 subtask. Các subtask được chia đều (NA tương ứng với không có subtask đó):

	Subtask 1	Subtask 2	Subtask 3	Subtask 4	Subtask 5
$k = 1$	$n\le 10^6$	NA	NA	NA	NA
$k = 2$	$n\le 5000$	$n\le 10^6$	NA	NA	NA
$k = 3$	$n\le 400$	$n\le 5000$	$n\le 10^4$	$n\le 10^5$	$n\le 10^6$
$k = 4$	$n\le 75$	$n\le 400$	$n\le 10^4$	$n\le 10^5$	$n\le 10^6$
$k = 5$	$n\le 30$	$n\le 75$	$n\le 10^4$	$n\le 10^5$	$n\le 10^6$
$k\le 10$	$n\le 5000$	$n\le 10^6$	NA	NA	NA

Sample 1

Input

5 6 3
2 3 1 2 2

Output

Note

Có 6 bộ 3 số thỏa mãn là $(1,2,3), (1,2,4), (1,2,5), (2,3,4), (2,3,5), (2,4,5)$

Sample 2

Input

10 3 5
1 2 3 4 5 6 7 8 9 10

Output

Note

Có tất cả 231 bộ 5 số thỏa mãn chia hết cho $3$

Bình luận

Không có bình luận nào.