// Move pragmas to the top, but REMOVE the "target" pragma to fix the compiler error. #pragma GCC optimize("O3,unroll-loops") #include<bits/stdc++.h> using namespace std; #define int long long using ll=int64_t; // Optimized Modular Integer template<int mod> struct mint { int32_t v; mint():v(0){} mint(ll _v):v((int32_t)(_v%mod)){ if(v<0) v+=mod; } mint& operator+=(const mint& o){ if((v+=o.v)>=mod)v-=mod; return *this; } mint& operator-=(const mint& o){ if((v-=o.v)<0)v+=mod; return *this; } mint& operator*=(const mint& o){ v = (int32_t)((ll)v*o.v%mod); return *this; } friend mint operator+(mint a, const mint& b){ return a+=b; } friend mint operator*(mint a, const mint& b){ return a*=b; } }; using mi = mint<998244353>; // GLOBAL STATIC ARRAYS (This is the most important optimization) const int MAXT = 205; mi dp1[11][MAXT][MAXT]; mi dp2[MAXT][MAXT][MAXT]; int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; if(!(cin >> n)) return 0; vector<string> s(2*n); vector<int> vis(256, 0); for(int i=0; i<n; i++){ cin >> s[i]; s[i+n] = s[i]; reverse(s[i+n].begin(), s[i+n].end()); for(auto x:s[i]){ vis[x]=1; } } sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end()); n = s.size(); int timer = 0; vector<int> pos(256); for(int i=0; i<256; i++){ if(vis[i]){ timer++; pos[i]=timer; } } // Fill dp1 for(int i=0; i<n; i++){ if(s[i].size() <= 10) { dp1[s[i].size()][pos[s[i][0]]][pos[s[i].back()]] += 1; } } mi ans = 0; // Main DP Logic for(int len=3; len<=10; len++){ // 1. Fill dp2 for(int32_t i=1; i<=timer; i++){ for(int32_t j=1; j<=timer; j++){ for(int32_t k=1; k<=timer; k++){ mi val = 0; for(int32_t x=1; x<=timer; x++){ val += dp1[len][x][i] * dp1[len][x][j] * dp1[len][x][k]; } dp2[i][j][k] = val; } } } // 2. Calculate ans (Optimized Order: x is outermost) for(int32_t x=1; x<=timer; x++){ for(int32_t i=1; i<=timer; i++){ for(int32_t k=1; k<=timer; k++){ mi term_xk = dp2[x][i][k]; for(int32_t j=1; j<=timer; j++){ ans += dp2[i][j][k] * term_xk * dp2[x][i][j] * dp2[x][j][k]; } } } } } cout << (int)ans.v << '\n'; }