#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[2003];
int dp[2005][2005];
const int mod=100000000;
int main(){
	int n,f;
	cin>>n>>f;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[i]=a[i]%mod;
	}
	for(int i=1;i<=n;i++)
	{
		dp[i][a[i]]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<f;j++)// yu shu
		{
			 dp[i][j]=((dp[i][j]+dp[i-1][j])%mod+dp[i-1][(j-a[i]+f)%f])%mod;
		}
	}
	cout<<dp[n][0]%mod;
	return 0;
}  

30pts，only ac #4 6 7！ need help qwq