Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem C: Biving’s Numbers

Problem C: Biving’s Numbers

Time Limit: 1 Sec  Memory Limit: 32 MB
Submit: 76  Solved: 33
[Submit][Status][Web Board]

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

HINT

[Submit][Status][Web Board]