#include <cstdio>

using namespace std;

FILE *in,*out;

const int modulo = 4001;

long long dp[1001][10];

int main()
{
    in = fopen("div3.in","r");
    out = fopen("div3.out","w");
    int n,l;
    fscanf(in,"%d %d",&n,&l);
    for(int i = 1;i <= n;i ++)
    {
        int x;
        fscanf(in,"%d",&x);
        dp[1][x % 3]++;
    }
    for(int i = 1;i <= l;i ++)
    {
        for(int j = 0;j <= 2;j ++)
        {
            for(int k = 0;k <= 2;k ++) {
                dp[i][j] += (dp[i-1][(3+j-k)%3] * dp[1][k])%modulo;
                dp[i][j] %= modulo;
            }
        }
    }
    fprintf(out,"%lld",dp[l][0]);
    return 0;
}