#include "bits/stdc++.h"
using namespace std;

#define ll long long 
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353

#define N 5050

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        string s; cin >> s;
        int n = s.length();
        int m = 0;
        for (auto c : s) m += c == '1';

        assert(m <= n);

        vector<vector<ll>> dp(n+10, vector<ll>(n+10, 0));

        for (int j = 0; j <= m; ++ j) dp[0][j] = j % 2 == m % 2 ? 1 : -1;
        for (int i = 1; i <= n; ++ i) {
            for (int j = 0; j <= m; ++ j) {
                if (s[i-1] == '1') {
                    if (j) dp[i][j-1] = (dp[i][j-1] + j * dp[i-1][j] % MOD) % MOD;
                    dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
                } else {
                    dp[i][j] = (dp[i][j] + j * dp[i-1][j] % MOD) % MOD;
                }
            }
        }

        cout << dp[n][0] << '\n';
    }
}