#include namespace { #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wunused-function" #include #pragma GCC diagnostic pop using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VL = vector; using VVL = vector; using mint = modint998244353; int m; struct S { bool first_ok[50]{}, second_ok[50]{}; mint cnt; int len = 0; friend S operator*(S x, S y) { S z; z.cnt = x.cnt + y.cnt; z.len = x.len + y.len; for(int i = 1; i < m; i++) if (x.first_ok[i] && y.second_ok[i]) { if (i <= x.len) { if (i + y.len >= m) { z.cnt++; } else { z.first_ok[i + y.len] = true; } } else { z.second_ok[i - x.len] = true; if (i + y.len < m) z.first_ok[i + y.len] = true; } } for(int i = 1; i < m; i++) if (m - i < x.len) z.second_ok[i] = x.second_ok[i]; for(int i = 1; i < m; i++) if (i < y.len) z.first_ok[i] = y.first_ok[i]; return z; } }; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; string t; cin >> t; m = t.size(); vector d(n); rep(z, n) { string s; cin >> s; if (s[0] == '~') { int j, k; cin >> j >> k; j--, k--; d[z] = d[j] * d[k]; } else { S A; int sz = s.size(); A.len = sz; auto chk = [&](int p1, int p2) { while(p1 < m && p2 < sz) if (t[p1++] != s[p2++]) return false; return true; }; for(int i = 1; i < m; i++) if (chk(i, 0)) { A.second_ok[i] = true; if (i + sz < m) A.first_ok[i + sz] = true; } for(int p = 0; p < sz; p++) if (chk(0, p)) { if (sz - p >= m) A.cnt++; else A.first_ok[sz - p] = true; } d[z] = A; } } mint ans = d[n - 1].cnt; cout << ans.val() << '\n'; }