#include<cstdio>
using namespace std;
#define N 300050
#define M 10
#define mod 1000000007
int dp[N][M],t[M][2],as;
char s[N];
int main()
{
	t[1][1]=2;t[1][0]=8;
	t[2][1]=3;t[2][0]=4;
	t[3][1]=3;t[3][0]=3;
	t[4][1]=2;t[4][0]=5;
	t[5][1]=4;t[5][0]=4;
	t[6][1]=2;t[6][0]=7;
	t[7][1]=6;t[7][0]=9;
	t[8][1]=6;t[8][0]=9;
	t[9][1]=8;t[9][0]=8;
	scanf("%s",s+1);
	dp[0][1]=1;
	for(int i=1;s[i];i++)
	{
		if(s[i]!='0')for(int j=1;j<10;j++)dp[i][t[j][1]]=(dp[i][t[j][1]]+dp[i-1][j])%mod;
		if(s[i]!='1')for(int j=1;j<10;j++)dp[i][t[j][0]]=(dp[i][t[j][0]]+dp[i-1][j])%mod;
		as=(dp[i][3]+dp[i][2])%mod;
	}
	printf("%d\n",as);
}//
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define MOD 998244353
using namespace std;
typedef long long ll;

template <typename Tp> inline void getint(Tp &num){
	register int ch, neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch & 15;
	while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
	if(neg) num = -num;
}

inline int fastpow(int bas, int ex){
	register int res = 1;
	for(; ex; ex >>= 1, bas = bas * (ll)bas % MOD) if(ex & 1) res = res * (ll)bas % MOD;
	return res;
}

inline int kazu(int a, const int &b) {return (a += b) >= MOD ? a - MOD : a;}
inline int hiku(int a, const int &b) {return (a -= b) < 0 ? a + MOD : a;}

int N, sum = 0, f[90005], g[90005];

int main(){
	getint(N), f[0] = g[0] = 1; 
	for(register int i = 1, a; i <= N; i++){
		getint(a), sum += a;
		for(register int j = sum; j >= 0; j--){
			f[j] = f[j] * 2LL % MOD;
			if(j >= a) f[j] = kazu(f[j], f[j - a]), g[j] = kazu(g[j], g[j - a]);
		}
	}
	int ans = fastpow(3, N);
	for(register int i = sum + 1 >> 1; i <= sum; i++) ans = hiku(ans, f[i] * 3LL % MOD);
	if(!(sum & 1)) ans = kazu(ans, g[sum >> 1] * 3LL % MOD);
	return printf("%d\n", ans), 0;
}