#include <cstdio>

#include <iostream>

#include <ctime>

#include <vector>

#include <cmath>

#include <map>

#include <queue>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long LL;

const int N=1e5+;

const int INF=0x3f3f3f3f;

const int mod=1e9+;

int f[N],a[N],d[];

int main()

{

    int n,m;

    while(~scanf("%d%d",&n,&m)){

       memset(d,,sizeof(d));

       int sum=,c=;

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

         scanf("%d",&a[i]);

         ++d[a[i]%];

         sum+=a[i]/;

         if(a[i]%==){

          if(a[i]>)++c;

         }

       }

       int ret=;

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

          int ans;

          if(i<=d[]+d[]+d[]+d[]){

             ans=d[]+d[]+d[]+d[]-i+d[]+d[]+d[]+sum*;

          }

          else {

             int k[];

             for(int j=;j<=;++j)k[j]=d[j];

              k[]=k[];k[]=;

              k[]+=k[];k[]=;

              k[]=;

              int tmp=sum-c;

              k[]+=c;k[]+=c;

              int t=i-d[]-d[]-d[]-d[];

              if(t<=k[]){

                k[]-=t;

                ans=tmp*+k[]+k[];

              }

              else {

                t-=k[];k[]=;

                int p=t/;

                if(tmp<=p){

                  p-=tmp;

                  tmp=;

                }

                else tmp-=p,p=;

                t=t%+p*;

                t/=;

                ans=max(,tmp*+k[]-t);

              }

          }

          ret=(ret+ans)%mod;

       }

       printf("%d\n",ret);

    }

    return ;

}