#include<cstdio>
using namespace std;
int data[1010],f[1010][1010];
 int n,m;

int main()
{ 
   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
    scanf("%d",&data[i]);
   data[i]%=m;
   
    f[i][data[i]]=1;
    
    } 
    for(int i=2;i<=n;i++)
       for(int j=m-1;j>=0;j--){
      if(j-data[i]<0)
{
       f[i][j]+=f[i-1][j]+f[i-1][j+m-data[i]];
       f[i][j]%=1234567;
}       
       else {
         f[i][j]+=f[i-1][j]+f[i-1][j-data[i]];
         f[i][j]%=1234567;
       }
      

       } 
       
       printf("%d",f[n][0]);
    return 0;
}