#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#include<queue>

using namespace std;

inline int read()

{

    int ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

const int mod=1e9+;

int n,key;

int a[];

int f[][];

int main()

{

    n=read();key=read();

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

      a[i]=read();

    f[][]=;

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

      for(int j=;j<key;j++)

      {

          int t=j-a[i]%key;

          if(t<) t=(t+key)%key;

          f[i][j]+=(f[i-][j]+f[i-][t])%mod;

      }

    printf("%d",f[n][]%mod);

    return ;

}