AT_past17_f 構文木

There is a $ N $ -vertex rooted binary tree whose vertices are numbered $ 1 $ through $ N $ . The root is vertex $ 1 $ , and the parent of vertex $ i $ $ (2 \leq i \leq N) $ is vertex $ p_i $ . Every vertex has **exactly zero or two** children. Vertex $ i $ has $ S_i $ written on it. $ S_i $ is either an integer or a character. If the vertex is a leaf, $ S_i $ is an integer; otherwise, it is either `+` or `x`. You will repeatedly perform the following two kinds of operations in any order, until you are unable to do so. - Choose a vertex, with `+` written on it, whose children both have integers written on them. Let $ a $ and $ b $ be those integers. Replace the `+` written on the vertex with the integer $ a+b $ , and remove the children. - Choose a vertex, with `x` written on it, whose children both have integers written on them. Let $ a $ and $ b $ be those integers. Replace the `x` written on the vertex with the integer $ a \times b $ , and remove the children. Once you are done, there will be only one remaining vertex with an integer written on it. Find this integer, modulo $ 998244353 $ . (One can prove that the integer written on the final vertex is unique regardless of the order of the operations.)

The input is given from Standard Input in the following format: > $ N $ $ p_2 $ $ p_3 $ $ \dots $ $ p_N $ $ S_1 $ $ S_2 $ $ \dots $ $ S_N $

Print the answer.

### Sample Explanation 1 By the following steps, there will be left a vertex with $ 13 $ written on it, so the answer is $ 13 $ . - Choose vertex $ 2 $ . Replace the `x` written on vertex $ 2 $ with $ 2 \times 5 = 10 $ , and remove vertices $ 4 $ and $ 5 $ . - Choose vertex $ 1 $ . Replace the `+` written on vertex $ 1 $ with $ 10 + 3 = 13 $ , and remove vertices $ 2 $ and $ 3 $ . ### Sample Explanation 2 Make sure to find the answer modulo $ 998244353 $ . ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq p_i \leq i - 1 $ $ (2 \leq i \leq N) $ - Every vertex occurs exactly zero times or twice in $ p_2, p_3, \dots, p_N $ . - $ S_i $ is: - an integer between $ 1 $ and $ 10^8 $ , inclusive, if vertex $ i $ is a leaf; - either `+` or `x` if vertex $ i $ is not a leaf.