void FFT(complex a[],int n,int fl){

      for (int i=,j=n/;i<n;i++){

        if (i<j) {complex t=a[i];a[i]=a[j];a[j]=t;};

        int k;

      for (k=(n>>);j&k;j^=k,k>>=);

      j^=k;

    }

     for (int i=;i<=n;i<<=){

      complex w;w.r=cos(fl**pi/i);w.i=sin(fl**pi/i);

      for (int j=;j<n;j+=i){

          complex wi;wi.r=;wi.i=;

          for (int k=j;k<j+i/;k++){

            complex u=a[k],v=a[k+i/]*wi;

          a[k]=u+v;a[k+i/]=u-v;

          wi=wi*w;

        }

      }

    }

    if (fl==-) for (int i=;i<n;i++) a[i].r/=n;

  }

void DFT(){

  for (int i=;i<n;i++){

      cp t=(cp){cos(*pi/n*i),sin(*pi/n*i)},bas=(cp){,};

      for (int j=;j<n;j++){

        tmp[i]=tmp[i]+bas*a[j];

      bas=bas*t;

    }

  }

  for (int i=;i<n;i++) a[i]=tmp[i];

}

void IDFT(){

  for (int i=;i<n;i++) P[i].r=P[i].i=;

  for (int i=;i<n;i++){

      cp t=(cp){cos(-*pi/n*i),sin(-*pi/n*i)},bas=(cp){,};

    for (int j=;j<n;j++){

      P[i]=P[i]+tmp[j]*bas;

      bas=bas*t;

    }

  }    

  for (int i=;i<n;i++) P[i].r=(int)(P[i].r/n+0.5);

}

#include <bits/stdc++.h>

#define LL long long

#define LDB long double

using namespace std;

  const LDB pi=acos(-);

  const LL mo=;

  int a[],n,k;

  struct data{

      LL a_1,a_n;

  };

  inline data operator*(data a,data b) {return((data){(a.a_n*b.a_n+a.a_1*b.a_1)%mo,(a.a_n*b.a_n+a.a_1*b.a_n+a.a_n*b.a_1)%mo});};

  struct cp{

      LDB r_1,r_n,r_n2,i_1,i_n,i_n2;

      void set0(){

        r_1=r_n=r_n2=i_1=i_n=i_n2=;

    }

    void set(data a){

      set0();

      r_1=a.a_1;r_n=a.a_n;

    }

  }A[],B[];

  inline cp operator *(cp a,cp b){

      return((cp)

      {

          a.r_1*b.r_1-a.i_1*b.i_1,

          a.r_n*b.r_1+a.r_1*b.r_n-a.i_n*b.i_1-a.i_1*b.i_n,

          a.r_n2*b.r_1+a.r_n*b.r_n+a.r_1*b.r_n2-a.i_n2*b.i_1-a.i_n*b.i_n-a.i_1*b.i_n2,

          a.r_1*b.i_1+a.i_1*b.r_1,

          a.r_n*b.i_1+a.r_1*b.i_n+a.i_n*b.r_1+a.i_1*b.r_n,

          a.r_n2*b.i_1+a.r_n*b.i_n+a.r_1*b.i_n2+a.i_n2*b.r_1+a.i_n*b.r_n+a.i_1*b.r_n2

      });

  }

  inline cp operator +(cp a,cp b){

      return((cp)

      {

          a.r_1+b.r_1,

          a.r_n+b.r_n,

          a.r_n2+b.r_n2,

          a.i_1+b.i_1,

          a.i_n+b.i_n,

          a.i_n2+b.i_n2,

      });

  }

  inline cp operator -(cp a,cp b){

      return((cp)

      {

          a.r_1-b.r_1,

          a.r_n-b.r_n,

          a.r_n2-b.r_n2,

          a.i_1-b.i_1,

          a.i_n-b.i_n,

          a.i_n2-b.i_n2,

      });

  }

  data getkth(int po){

      data ret;ret.a_1=;ret.a_n=;

      data bas;bas.a_1=;bas.a_n=;

      for (;po;bas=bas*bas){

        if (po&) ret=ret*bas;

      po>>=;

    }

    return(ret);

  }

   void FFT(cp a[],int n,int fl){

    for (int i=,j=n/;i<n;i++){

      if (i<j) {cp t=a[i];a[i]=a[j];a[j]=t;};

      int k;

      for (k=(n>>);j&k;j^=k,k>>=);

      j^=k;

    }

     for (int i=;i<=n;i<<=){

      cp w;w.set0();

      w.r_1=cos(fl**pi/i);w.i_1=sin(fl**pi/i);

      for (int j=;j<n;j+=i){

        cp wi;wi.set0();

        wi.r_1=;wi.i_1=;

        for (int k=j;k<j+i/;k++){

          cp u=a[k],v=a[k+i/]*wi;

          a[k]=u+v;a[k+i/]=u-v;

          wi=wi*w;

        }

      }

    }

    if (fl==-) for (int i=;i<n;i++) a[i].r_n2/=n,a[i].r_n/=n,a[i].r_1/=n;

  }

  vector <data> MUL(vector <data> &a,vector <data> &b){

      int n=;

      while (n<a.size()+b.size()) n<<=;

      for (int i=;i<n;i++){

        if (i<a.size()) A[i].set(a[i]);else A[i].set0();

      if (i<b.size()) B[i].set(b[i]);else B[i].set0();

    }

    FFT(A,n,);FFT(B,n,);

    for (int i=;i<n;i++) A[i]=A[i]*B[i];

    FFT(A,n,-);

    vector <data> ret;ret.resize(a.size()+b.size());

    for (int i=;i<a.size()+b.size();i++){

      LL tn2=(A[i].r_n2+0.5),tn=(A[i].r_n+0.5),t1=(A[i].r_1+0.5);

      ret[i].a_n=(tn2+tn)%mo;ret[i].a_1=(tn2+t1)%mo;

    }

    return(ret);

  }

  void show(vector <data> tmp1,vector <data> tmp2){

      for (int i=;i<tmp1.size();i++) printf("%lld %lld|",tmp1[i].a_n,tmp1[i].a_1);printf("\n");

      for (int i=;i<tmp2.size();i++) printf("%lld %lld|",tmp2[i].a_n,tmp2[i].a_1);printf("\n");

      vector <data> res=MUL(tmp1,tmp2);

      for (int i=;i<res.size();i++) printf("%lld %lld|",res[i].a_n,res[i].a_1);printf("\n\n");

  }

  vector <data> solve(int l,int r){

      if (l==r){

        vector <data> ret;ret.resize();

      ret[].a_1=;ret[].a_n=;

      ret[]=getkth(a[l]);

      return(ret);

    }

    int mid=(l+r)>>;

    vector <data> tmp1=solve(l,mid);

    vector <data> tmp2=solve(mid+,r);

//    show(tmp1,tmp2);

    return(MUL(tmp1,tmp2));

  }

  int main(){

      scanf("%d%d",&n,&k);

      for (int i=;i<=n;i++) scanf("%d",&a[i]);

      vector <data> ans=solve(,n);

      printf("%lld\n",ans[k].a_n%mo);

  }