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]