#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <functional>
#include <sstream>
#include <fstream>
#include <valarray>
#include <complex>
#include <queue>
#include <cassert>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define debug_flag 1
#else
	#define debug_flag 0
#endif

template <class T1, class T2 >
std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p)
{
	os << "[" << p.first << ", " << p.second << "]";
	return os;
}

template <class T >
std::ostream& operator << (std::ostream& os, const std::vector<T>& v)
{
	os << "[";
	bool first = true;
	for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
	{
		if (!first)
			os << ", ";
		first = false;
		os << *it;
	}
	os << "]";
	return os;
}

#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }

vector<string> _split(const string& s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c))
		v.emplace_back(x);
	return v;
}

void _print(vector<string>::iterator) {}
template<typename T, typename... Args>
void _print(vector<string>::iterator it, T a, Args... args) {
    string name = it -> substr((*it)[0] == ' ', it -> length());
    if (isalpha(name[0]))
	    cerr << name  << " = " << a << " ";
	else
	    cerr << name << " ";
	_print(++it, args...);
}

typedef long long int int64;

const int bs = 1000000007;

const int N = 105;
const int K = 10;
const int M = 31;

int n,m,k;
int D[N];
int dp[N][1<<K][M];
int precalc[1<<K];

void add(int&a,int b)
{
	a+=b;
	if (a>=bs)
		a-=bs;
}

int main()
{
#ifdef LOCAL
	freopen ("input.txt", "r", stdin);
#endif

	cin>>n>>m>>k;
	for (int i=1;i<n;i++)
	{
		cin>>D[i];
	}

	for (int mask=0;mask<(1<<k);mask++)
	{
		int crosses=0;

		for (int i=0;i+1<k;i++)
		{
			int v1=(mask&(1<<i));
			int v2=(mask&(1<<(i+1)));
			if (v1>1)
				v1=1;
			if (v2>1)
				v2=1;
			if (v1!=v2)
				crosses++;
		}
		precalc[mask]=crosses;
	}

	for (int mask=0;mask<(1<<k);mask++)
	{
	//	dbg(mask,precalc[mask]);
	}

	dp[0][0][0]=1;
	for (int i=0;i<n;i++)
	{
		for (int mask=0;mask<(1<<k);mask++)
		{
			for (int rem=0;rem<m;rem++)
			{
				if (dp[i][mask][rem])
				{
				//	dbg(i,mask,rem,dp[i][mask][rem]);
				}
				int new_rem=rem;
				new_rem+=precalc[mask]*D[i];
				new_rem%=m;
				// don't take
				add(dp[i+1][mask][new_rem],dp[i][mask][rem]);
				// take at x
				for (int x=0;x<k;x++)
				{
					if (!(mask&(1<<x)))
					{
						add(dp[i+1][mask|(1<<x)][new_rem],dp[i][mask][rem]);
					}
				}
			}
		}
	}

	cout<<dp[n][(1<<k)-1][0]<<endl;

	return 0;
}