#include<bits/stdc++.h>
using namespace std;
int n,F,a[2010];
const int p=(int)1e8;
int dfs(int dep,int sum){
	if(dep==n){
		if(sum==0){
			return 0;
		}if(sum%F==0){
			return 1;
		}
		return 0;
	}
	return dfs(dep+1,sum+a[dep])+dfs(dep+1,sum);
}
int main(){
	scanf("%d%d",&n,&F);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	printf("%d\n",dfs(0,0)%p);
	return 0;
}