//#include <atcoder/all>
#include <bits/stdc++.h>

using namespace std;


#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

typedef long long  ll; typedef vector<int> VI; typedef pair<int,int> pii; typedef vector<ll> VL; const int MD = 1e9+7; //998244353;
void dbg(){cerr<<"\n";} template <class F,class ...S> void dbg(const F& f, const S&...s){cerr <<f <<": "; dbg(s...);}

//using mint = atcoder::modint1000000007;

ll fnc(){
	ll n;
	string t;
	cin >>n >>t;
	ll mx=(ll)1e10;
	
	if(t=="1") return 2*mx;
	if(t=="11" ||t=="0"|| t=="110") return mx;
	
	string s;
	rep(i, (n+11)/3) s +="110";
	if(s.find(t) ==string::npos) return 0;
	int zct=0;
	for(auto x:t) zct += x=='0';
	ll ans = mx - zct +(t[n-1]=='0'? 1: 0);
	return ans;
}


int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	cout << fnc() <<"\n";
	return 0;
}

#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 998244353
using namespace std;
using ll = long long;

template<int M>
class ModInt {
   public:
    ll value;
    constexpr ModInt(ll v = 0) { value = v % M; if (value < 0) value += M; }
    constexpr ModInt pow(ll n) const { if (!n) return 1; ModInt a = pow(n >> 1); a *= a; if (n & 1) a *= *this; return a; }
    constexpr ModInt inv() const { return this->pow(M - 2); }
    constexpr ModInt operator + (const ModInt &rhs) const { return ModInt(*this) += rhs; };
    constexpr ModInt operator - (const ModInt &rhs) const { return ModInt(*this) -= rhs; };
    constexpr ModInt operator * (const ModInt &rhs) const { return ModInt(*this) *= rhs; };
    constexpr ModInt operator / (const ModInt &rhs) const { return ModInt(*this) /= rhs; };
    constexpr ModInt &operator += (const ModInt &rhs) { value += rhs.value; if (value >= M) value -= M; return *this; };
    constexpr ModInt &operator -= (const ModInt &rhs) { value -= rhs.value; if (value <  0) value += M; return *this; };
    constexpr ModInt &operator *= (const ModInt &rhs) { value = value * rhs.value % M; return *this; };
    constexpr ModInt &operator /= (const ModInt &rhs) { return (*this) *= rhs.inv(); };
    constexpr bool operator == (const ModInt &rhs) { return value == rhs.value; }
    constexpr bool operator != (const ModInt &rhs) { return value != rhs.value; }
    friend ostream &operator << (ostream &os, const ModInt &rhs) { os << rhs.value; return os; }
};

using mint = ModInt<MOD>;

int main() {
    int N, K; cin >> N >> K;
    vector<int> A(N);
    REP(i, 0, N) cin >> A[i];

    vector<mint> B(N, 1), C(N, 1), D(K + 1, 0), E(K + 1, 0);
    D[0] = N; E[0] = N;
    mint fac = 1;
    REP(i, 0, K) {
        REP(j, 0, N) {
            B[j] *= (2 * A[j]);
            C[j] *= A[j];
            D[i + 1] += B[j];
            E[i + 1] += C[j];
        }
        
        fac *= mint(i + 1);
        E[i + 1] /= fac;
    }

    fac = 1;
    REP(i, 1, K + 1) {
        mint ans = fac;
        mint tmp = 0;
        REP(j, 0, i + 1) {
            tmp += E[j] * E[i - j];
        }
        ans *= tmp;
        // cout << "# i : " << i << ", ans : " << ans << " - " << D[i] << " / " << 2 << endl;
        ans -= D[i];
        ans /= mint(2);
        cout << ans << endl;
        fac *= mint(i + 1);
    }
    return 0;
}