#include "bits/stdc++.h"

#define endl "\n"
#define int long long
#define double long double
#define precise \
    fixed << setprecision(12)
#ifndef ONLINE_JUDGE
#define debug(var) cerr << (#var) << ": " << var << endl
#else
#define debug(var)
#endif

using namespace std;

template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using max_heap = priority_queue<T>;

template <class T>
ostream &operator<<(ostream &os, min_heap<T> H)
{
    while (!H.empty())
    {
        os << H.top() << " ";
        H.pop();
    }
    os << endl;
    return os << "";
}

template <class T>
ostream &operator<<(ostream &os, max_heap<T> H)
{
    while (!H.empty())
    {
        os << H.top() << " ";
        H.pop();
    }
    os << endl;
    return os << "";
}

template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P)
{
    return os << P.first << " " << P.second;
}

template <class T>
ostream &operator<<(ostream &os, vector<T> arr)
{
    for (int i = 0; i < (int)arr.size(); i++)
    {
        os << arr[i] << " ";
    }
    return os << "";
}

template <class T>
ostream &operator<<(ostream &os, vector<vector<T>> matrix)
{
    os << endl;
    for (int i = 0; i < (int)matrix.size(); i++)
    {
        for (int j = 0; j < (int)matrix[i].size(); j++)
        {
            os << matrix[i][j] << " ";
        }
        os << endl;
    }
    return os << "";
}

template <class T>
ostream &operator<<(ostream &os, set<T> S)
{
    for (auto s : S)
    {
        os << s << " ";
    }
    return os << "";
}

template <class T>
ostream &operator<<(ostream &os, multiset<T> S)
{
    for (auto s : S)
    {
        os << s << " ";
    }
    return os << "";
}

template <class L, class R>
ostream &operator<<(ostream &os, map<L, R> M)
{
    os << endl;
    for (auto m : M)
    {
        os << m << endl;
    }
    return os << "";
}

template <class L, class R>
ostream &operator<<(ostream &os, multimap<L, R> M)
{
    os << endl;
    for (auto m : M)
    {
        os << m << endl;
    }
    return os << "";
}

const int max_n = 2e5;
// const int mod = 1e9 + 7;
const int mod = 998244353;

inline int add(int val1, int val2)
{
    int ans = val1 + val2;
    if (ans >= mod)
    {
        ans -= mod;
    }
    return ans;
}

inline int sub(int val1, int val2)
{
    int ans = val1 - val2;
    if (ans < 0)
    {
        ans += mod;
    }
    return ans;
}

inline int mult(int val1, int val2)
{
    int ans = (val1 * 1LL * val2) % mod;
    return ans;
}

inline int power(int base, int val)
{
    base = base % mod;
    int res = 1;
    while (val > 0)
    {
        if ((val & 1))
        {
            res = mult(res, base);
        }
        base = mult(base, base);
        val = (val >> 1);
    }
    return res;
}

inline int modInverse(int num)
{
    return power(num, mod - 2);
}

inline int divide(int val1, int val2)
{
    int val3 = modInverse(val2);
    int ans = mult(val1, val3);
    return ans;
}

vector<int> factorial(max_n + 1);
vector<int> mmi(max_n + 1);
void calculate_factorial()
{
    factorial[0] = 1;
    mmi[0] = 1;
    for (int i = 1; i <= max_n; i++)
    {
        factorial[i] = mult(factorial[i - 1], i);
    }
    mmi[max_n] = modInverse(factorial[max_n]);
    for (int i = max_n - 1; i >= 1; i--)
    {
        mmi[i] = mult(mmi[i + 1], i + 1);
    }
}

int nCr(int n, int r)
{
    if (n < r)
        return 0;
    if (r == 0)
        return 1;

    return mult(mult(factorial[n], mmi[r]), mmi[n - r]);
}

void solve()
{
    int n;
    cin >> n;
    string x;
    cin >> x;
    x = '0' + x + '0';
    int prt[2] = {0, 0};
    int cnt[2] = {0, 0};
    int last = 0;
    for (int i = 1; i <= n + 1; i++)
    {
        if (x[i] == '0')
        {
            int len = i - 1 - last;
            prt[len % 2]++;
            last = i;
        }
        cnt[x[i] - '0']++;
    }
    cnt[0]--;
    if (prt[1] == 0)
    {
        cout << nCr(cnt[1] / 2 + prt[0] - 1, prt[0] - 1) << endl;
        return;
    }

    if (prt[0] == 0)
    {
        cout << nCr((cnt[1] - prt[1]) / 2 + prt[1] - 1, prt[1] - 1) << endl;
        return;
    }

    int ans = 0;
    for (int i = prt[1]; i <= cnt[1]; i++)
    {
        int give_odd = i - prt[1];
        int give_even = cnt[1] - i;
        if (give_odd % 2 != 0 || give_even % 2 != 0)
        {
            continue;
        }
        give_odd /= 2;
        give_even /= 2;

        ans = add(ans, mult(nCr(give_odd + prt[1] - 1, prt[1] - 1), nCr(give_even + prt[0] - 1, prt[0] - 1)));
    }
    cout << ans << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    calculate_factorial();
    // freopen("input.in", "r", stdin);
    // freopen("output.out", "w", stdout);
    int no_of_testcases = 1;
    cin >> no_of_testcases;
    for (int i = 1; i <= no_of_testcases; i++)
    {
        // cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}