#include <iostream>
#include <string>
#include <cmath>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <utility>

using namespace std;
long long mod = 998244353;
long long modInverse(long long a, long long m)
{
	long long m0 = m;
	long long y = 0, x = 1;

	if (m == 1)
		return 0;

	while (a > 1) {
		// q is quotient
		long long q = a / m;
		long long t = m;

		// m is remainder now, process same as
		// Euclid's algo
		m = a % m, a = t;
		t = y;

		// Update y and x
		y = x - q * y;
		x = t;
	}

	// Make x positive
	if (x < 0)
		x += m0;

	return x;
}
long long nChoosek(long long n, long long k)
{
	if (k > n) return 0;
	if (k * 2 > n) k = n - k;
	if (k == 0) return 1;

	long long result = n;
	for (long long i = 2; i <= k; ++i) {
		result *= (n - i + 1);
		result %= mod;
		result *= modInverse(i, mod);
		result %= mod;
	}
	return result;
}
int main() {
	long long testcases;
	cin >> testcases;
	for (long long casenum = 0; casenum < testcases; casenum++) {
		long long n;
		cin >> n;
		string s;
		cin >> s;
		long long o = 0; // number of odd groups
		long long t = 0; // number of total ones
		long long r = 0; // running group size
		for (long long i = 0; i < n; i++) {
			if (s[i] == '1') {
				r++;
				t++;
			} else if (r > 0) {
				if (r % 2 == 1) o++;
				r = 0;
			}
		}
		if (r % 2 == 1) o++;
		long long e = (t - o) / 2; // number of pairs
		//answer is (n-o-e) choose e
		long long ans = 1;
		long long c1 = n - o - e;
		cout << nChoosek(c1, e) << endl;

	}
}
