#include <fstream>
using namespace std;
ifstream cin("div3.in");
ofstream cout("div3.out");
int d[1001][3];
int main()
{
    int n,m,i,j,p,c,k,s=0;
    cin>>n>>p;
    m=4001;
    for(i=1;i<=n;i++)
    {
        cin>>c;
        d[1][c%3]++;
    }
    for(i=2;i<=p;i++)
        for(j=0;j<3;j++)
            for(k=0;k<3;k++)
                d[i][j]=(d[i][j]+d[i-1][k]*d[1][(j-k+3)%3])%m;
    cout<<d[p][0];
    return 0;
}