Eternal Tree

This problem involves an eternal tree with n nodes. Each node x (1 ≤ x ≤ n) is associated with an eternal string S(x). The eternal value of a string is defined as its length:

[ f(S) = \mathrm{Len}(S) ]

For an undirected simple path \(K=[u,v]\) in the tree (with u < v) — that is, the unique simple path connecting u and v — its eternal value is defined as the sum over all unordered pairs of distinct nodes \((x,y)\) on the path (with x < y) of the eternal value of their longest common prefix (LCP):

[ f(K)=\sum_{x,y\in K,; x<y} f(\mathrm{LCP}(S(x),S(y))) = \sum_{x,y\in K,; x<y} \mathrm{Len}(\mathrm{LCP}(S(x),S(y))) ]

The eternal value of the tree is defined as the sum over all undirected simple paths in the tree:

[ f(T)=\sum_{u,v\in T,; u<v} f([u,v]) ]

It is given that the string on each node comes from an eternal Trie (prefix tree) with node 1 as its root. In other words, the tree structure is exactly that of the Trie and for every non‐root node i (2 ≤ i ≤ n) the string S(i) = S(p) + c, where p is the parent of node i and c is a lowercase letter.

Your task is to calculate the eternal value of the tree modulo 998244353.

inputFormat

The first line contains a single integer n, the number of nodes in the tree.

The second line contains a nonempty string representing S(1), the string at node 1.

For nodes 2 to n, each of the next n-1 lines contains an integer p and a lowercase letter c, meaning that node i's parent is p and S(i) = S(p) + c.

Note: The tree is undirected but its structure is given by the parent relation from the Trie.

outputFormat

Output a single integer: the eternal value of the tree (i.e. f(T)) modulo 998244353.

sample

3
a
1 a
1 b

5