#include<bits/stdc++.h>

    using namespace std;
    const int N=2e5+10,mod=998244353;
    int n, m, k;

    void solve() {
        string s;
        cin >> s;
        n = s.size();
        vector<vector<int>> dp(5000+10, vector<int>(5000+10));
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i].assign(n + 1, 0);
            for (int j = 0; j <= i; j++) {
                dp[i][j] = (1ll * j * dp[i-1][j] + (j ? dp[i-1][j - 1] : 0)) % mod;
                if (s[i - 1] == '1') {
                    dp[i][j] = (dp[i][j] + 1ll * j * dp[i-1][j] + 1ll * (j + 1) * (j + 1) * dp[i-1][j + 1]) % mod;
                }
            }
        }
        cout << dp[n][0] << endl;
    }

    int main() {  
        cin.tie(0);
        cout.tie(0);
        ios::sync_with_stdio(0);
        int _;
        _ = 1;
        cin >> _;
        while(_ --) {
            solve();
        }
        return 0;
    }