#include <fstream>
#define Mod 999983

using namespace std;
ifstream f("tango.in");
ofstream g("tango.out");

int n,k,p,v[40],frec[10],st[40];
long long nr;

long long lgput(long long x,long long y)
{
    long long m=1;
    while (y>1)
    {
        if (y%2==0)
        {
            x=(x*x)%Mod;
            y=y/2;
        }
        else
        {
            m=(m*x)%Mod;
            --y;
        }
    }
    return (m*x)%Mod;
}

void afisare(int k)
{
    for (int i=1; i<=k; ++i) g<<st[i]<<' ';
    g<<'\n';
}

void Back(int k, int suma)
{
    if (suma==8)
    {
        //afisare(k-1);
        ++nr;
        return;
    }
    for (int i=1; i<=n; ++i)
        if (suma+v[i]<=8) Back(k+1,suma+v[i]);
}

int main()
{
    f>>n>>k;
    p=k/8;


    if (n<=30)
    {
        for (int i=1; i<=n; ++i)
        {
            f>>v[i];
            ++frec[v[i]];
        }
        nr=0;
        Back(1,0);
        //g<<nr<<' '<<p<<'\n';
        g<<lgput(nr,p)<<'\n';
    }
    else
    {
        for (int i=1; i<=n; ++i)
        {
            int x;
            f>>x;
            ++frec[x];
        }
        nr=0;
        if (frec[8]>0) nr=frec[8];
        if (frec[4]>1) nr=(nr+lgput(frec[4],2))%Mod;
        if (frec[6]>0 && frec[2]>0)
        {
            long long produs=(frec[6]*frec[2])%Mod;
            nr=(nr+produs*2)%Mod;
        }
        if (frec[2]>3)nr=(nr+lgput(frec[2],4))%Mod;
        if (frec[4]>0 && frec[2]>1)
        {
            long long produs=(lgput(frec[2],2)*frec[4])%Mod;
            nr=(nr+produs*3)%Mod;
        }
        g<<lgput(nr,p)<<'\n';

    }
    f.close();
    g.close();
    return 0;
}