#include <bits/stdc++.h>
using namespace std;int n,m,a[2005];long long dp[2005][1005];const int mod=1e8;int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];a[i]%=m;dp[i][a[i]]=1;}for(int i=1;i<=n;i++){for(int j=0;j<m;j++){long long sum=dp[i-1][(j+m-a[i])%m]+dp[i-1][j]+dp[i][j];sum%=mod;dp[i][j]=sum;}}cout<<dp[n][0]<<"\n";return 0;}