#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll num[200005],f,ans,n,dp[70000000],maxx;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>f;
	for(ll i=1;i<=n;i++){
		cin>>num[i];
		if(num[i]!=f)num[i]%=f;
		maxx+=num[i];
	}
	for(ll i=1;i<=n;i++){
		for(ll j=maxx;j>=1;j--){
			dp[j+num[i]]+=dp[j];
		}
		dp[num[i]]++;	
//		for(ll i=1;i<=maxx;i++)cout<<dp[i]<<" ";
//		cout<<endl;
	}
//	for(ll i=1;i<=maxx;i++)cout<<dp[i]<<" ";
//	cout<<endl;
	for(ll i=f;i<=maxx;i+=f){
		ans+=dp[i];
		ans%=100000000;
	}
	cout<<ans;
	return 0;
}
/*
13 5
1 5 3 6 2 6 2 4 21 3 4 5 8
*/