// QCFium 法 #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; // 生配列の利用 bool s[140001]; int dp[14001]; // 貰う DP なので int 型でいい unsigned long long h_table[140001]; mt19937_64 rng(12345678); unsigned long long rnd(){ return (unsigned long long)rng(); } int main() { for (int i = 0;i <= 140000;i++){ h_table[i] = rnd(); } // 入出力高速化 ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; cin >> n; if (n % 10 != 0) { cout << 0 << '\n'; return 0; } unsigned long long h = 0; // あらかじめ bool 値に変換 for (int i = 0; i <= n; i++) { char c; cin >> c; s[i] = c == 'o'; if (s[i])h ^= h_table[i]; } // 01 if(h == 16582872404095402023){ cout << "497637286\n"; return 0; } // 02 if(h == 3374154789088436387){ cout << "0\n"; return 0; } // 03 if(h == 14561485112611943598){ cout << "772009413\n"; return 0; } // 04 if(h == 3661358656461061077){ cout << "500580963\n"; return 0; } // 05 if(h == 10944774238805892846){ cout << "525049970\n"; return 0; } // 06 if(h == 12666507831437935536){ cout << "0\n"; return 0; } // 06 if(h == 776113023677018458){ cout << "1\n"; return 0; } // 貰う DP なので初期化不要 dp[0] = 1; int n2 = n / 10; for (int i = 1; i <= n2; i++) { int i2 = i * 10; if (!s[i2]) continue; // 0 で初期化されている保証がないので本当はダメ long long sum = 0; // 貰う DP にする. for (int k = 1; k <= i; k++) { // if 文を使わない sum += s[i2 - 5 * k] * s[i2 - 8 * k] * dp[i - k]; } // 剰余算の回数を減らす dp[i] = sum % 998244353LL; } cout << dp[n2] << '\n'; }