tango

#include <cstdio>
#define NMAX 100003
#define m 999983
using namespace std;
long long n,k,i,j,nr,poz;
long long v[NMAX];
long long x[10];

long long exponentiere(){
    long long i,nr=k/8,aux=x[8],sol=1;
    for(i=0;(1<<i)<=nr;i++){
        if((1<<i) & nr)
            sol=(sol*aux)%m;
        aux=(aux*aux)%m;
    }
    return sol;
}

int main()
{
    freopen("tango.in","r",stdin);
    freopen("tango.out","w",stdout);
    scanf("%lli%lli",&n,&k);
    for(i=1;i<=n;i++)
        scanf("%lli",&v[i]);
    x[0]=1;
    for(i=1;i<=8;i++){
        for(j=1;j<=n;j++){
            poz=i-v[j];
            if(poz>=0)
                x[i]=(x[i]+x[poz])%m;
        }
    }
    printf("%lli",exponentiere());
    return 0;
}