文理学院程序设计在线练习


Biving’s Numbers

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 15   Accepted Submission(s): 11
Problem Description

Biving loves her numbers. She always plays with them and treat them as her precious treasure.
Biving has N (1 <= N <= 13) numbers. One day, Biving wants to select K (1 <= K <= N) of them and wonders how many ways she can find such that the sum of these selected numbers have some common divisor with a given number M (1 <= M <= 10^7) besides 1.

Input

The input contains several test cases (<= 100). Each test case have three integers in the first line: N, K and M. The next line contains N integers separated by a whitespace. Each number Ni will be in the following range: (1 <= Ni <= 10^7).

Output

The output contains an integer, the answer for each case given in the input.

Sample Input
3 2 2
1 1 1
5 2 10
1 2 3 4 5
Sample Output
3
6
Source

2013绍兴市赛