#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 5010
#define mod 998244353
#define LL long long
const int w=15;
int n,m,fac[N],ifac[N],f[20][N];
inline int quick_pow(int x,int b)
{
	int ret=1;
	while(b)
	{
		if(b&1) ret=(LL)ret*x%mod;
		x=(LL)x*x%mod,b>>=1;
	}
	return ret;
}
inline int inv(int x) {return quick_pow(x,mod-2);}
void init(int n)
{
	fac[0]=1;
	for(int i=1;i<=n;++i)
		fac[i]=(LL)fac[i-1]*i%mod;
	ifac[n]=inv(fac[n]);
	for(int i=n;i;--i)
		ifac[i-1]=(LL)ifac[i]*i%mod; 
}
inline int C(int n,int m)
{
	return n<m?0:(LL)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
inline void add(int &a,int b) {a+=b;if(a>=mod) a-=mod;}
int main()
{
	scanf("%d %d",&n,&m);
	init(n),f[0][0]=1;
	for(int i=0;i<w;++i)
		for(int k=0;(1<<i)*k<=m;k+=2)
			for(int j=0;j+(1<<i)*k<=m;++j)
				add(f[i+1][j+(1<<i)*k],(LL)f[i][j]*C(n,k)%mod);
	printf("%d",f[w][m]);
	return 0;
}
#include <bits/stdc++.h>

#define int long long
#define debug(x) cout << #x << " = " << x << endl;
using namespace std;

inline int read() {
   int s = 0, w = 1;
   char ch = getchar();
   while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
   while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

int const MAXN = 2e5 + 10, mod = 1e9 + 7;
int n, m, T, dp[MAXN][2], cnt[MAXN][2], a[MAXN];
// cnt[i][0] +, cnt[i][1] -
// dp[i][0] +, dp[i][1] -

signed main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    cnt[1][0] = 1, dp[1][0] = a[1];
    for (int i = 2; i <= n; ++i) {
        cnt[i][0] = cnt[i - 1][1] + cnt[i - 1][0];
        cnt[i][0] %= mod;
        cnt[i][1] = cnt[i - 1][0];
        cnt[i][1] %= mod;

        dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + a[i] * cnt[i][0];
        dp[i][0] %= mod;
        dp[i][1] = dp[i - 1][0] - a[i] * cnt[i][1];
        dp[i][1] %= mod;
    }
    cout << ((dp[n][0] + dp[n][1] )% mod + mod) % mod;
    return 0;
}