#include<bits/stdc++.h>
using namespace std;
long long dp[2005][2005]={1};
int main()
{
	int n,i,j,f,w[2005]={0};
	cin>>n>>f;
	for(i=1;i<=n;i++)
	{
		cin>>w[i];
		w[i]%=f;
	}
	for(i=1;i<=n;i++)
		for(j=0;j<f;j++)
			dp[i][j]=(dp[i][j]+dp[i-1][j]+dp[i-1][(j-w[i]+f)%f])%100000000;
	cout<<dp[n][0];
}