finding sum:

finding sum: 

Problem Description

You are given a set of N positive integers and another integer P, where P is a small prime. You need to write a program to count the number of subsets of size (cardinality) 3, the sum of whose elements is divisible by P. Since the number K of such sets can be huge, output K modulo 10007 1009 (the remainder when K is divided by 1009)

Constraints

N <= 500

P<50

All integers <=1000

Input Format

First line two comma separated integers N, P

The next line contains N comma separated integers

Output

One integer giving the number of subsets the sum of whose elements is divisible by P. Give result modulo 1009

Explanation

Example 1

Input

4,5

5,10,15,20

Output

4

Explanation

Every non empty subset of the given numbers has sum of its elements a multiple of 5. Since there are 4 subsets of size 3, the output is 4.

Example 2

Input

5,5

3,7,12,13,15

Output

4

Explanation

There are 4 subsets of size 3 with sum a multiple of 5: {3, 7, 15}, {12, 13, 15}, {7, 13, 15}, {3, 12, 15}, Hence the output is 4.

 Solution 

#include<stdio.h>

 int main()

{ 

int n,i,j,k,sum=0,a[100],p,c=0; 

scanf("%d,%d\n",&n,&p); 

for(i=0;i<n;i++) 

 { 

 scanf("%d,",&a[i]);

 }

 for (i = 0; i < n; i++) 

 {

 for (j = i + 1; j < n;)

 {

 if (a[j] == a[i])

 { 

for (k = j; k < n; k++)

 {

 a[k] = a[k + 1]; } n--;

 }

 else j++;

 }

 }

 for(i=0;i<n;i++)

 { 

 for(j=i+1;j<n;j++)

 {

 for(k=j+1;k<n;k++)

 { 

sum=a[i]+a[j]+a[k];

 if(sum%p==0) c++;

 sum=0; 

 }

  }

 }

 printf("%d",c);

 return 0;

 }