#include <fstream>
#include <iostream>

using namespace std;

ifstream in("div3.in");
ofstream out("div3.out");

long long d[1003][4],a[1003],n,m;
int km[505][505];

void citire()
{
    in>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        in.getline(a,256);
        km[i][1]=(int)c[1];
        km[i][2]=(int)c[2];
    }
}

int main()
{
    citire();
    for(int i=1; i<=n; ++i)
    {
        int r=a[i]%3;
        d[1][r]++;
    }
    for(int i=2; i<=m; ++i)
        for(int j=0; j<=2; ++j)
            for(int k=0; k<=2; ++k)
            {d[i][j]+=d[i-1][k]*d[1][(j-k+3)%3]; d[i][j]%=4001;}


    out<<d[m][0];
    return 0;

}