DeadLine

题目描述

There are $n$ states numbered $1,2,\ldots,n$. Initially, the process is at state $1$.

Each operation increases the number of performed operations by $1$, and then the next state is determined as follows:

• If the current state is $1$, the process always moves to state $2$ after the operation.
• If the current state is $n$, the process terminates after the operation.
• For each state $i$ such that $2\le i\le n-1$, two values $A_i$ and $P_i$ are associated with it. After an operation at state $i$, the process moves to state $i+1$ with probability $P_i$, and moves to state $A_i$ with probability $1-P_i$. It is guaranteed that $1\le A_i \lt i$.

For a fixed sequence of probabilities $P_2,P_3,\ldots,P_{n-1}$, let $f(P_2,P_3,\ldots,P_{n-1})$ be the expected number of operations needed until the process terminates, starting from state $1$.

You are given an array of length $n-2$: $P'_1,P'_2,\ldots,P'_{n-2}.$ A permutation $p$ of length $n-2$ is chosen uniformly at random. Then the probabilities of the internal states are assigned by $P_{i+1}=P'_{p_i} (1\le i\le n-2).$

If several values in $P'$ are equal, they are still treated as different elements according to their indices. In other words, all permutations of indices are counted separately.

Your task is to compute $\frac{1}{(n-2)!}\sum_{p\in S_{n-2}} f(P'_{p_1},P'_{p_2},\ldots,P'_{p_{n-2}}) \pmod {998244353}.$

输入格式

The first line contains one integer $n$ ($2\le n\le 5000$).

The second line contains $n-2$ integers $A_2,A_3,\ldots,A_{n-1}$ ($1\le A_i \lt i$).

The third line contains $n-2$ integers $P'_1,P'_2,\ldots,P'_{n-2}$ ($2\le P'_i \lt 998244353$), denoting the probabilities modulo $998244353$.

输出格式

The first line contains one integer $n$ ($2\le n\le 5000$).

The second line contains $n-2$ integers $A_2,A_3,\ldots,A_{n-1}$ ($1\le A_i \lt i$).

The third line contains $n-2$ integers $P'_1,P'_2,\ldots,P'_{n-2}$ ($2\le P'_i \lt 998244353$), denoting the probabilities modulo $998244353$.

样例输入 #1

4
1 1
499122177 499122177

样例输出 #1

11

样例输入 #2

10
1 2 3 1 4 2 1 3
862701445 502573809 116853317 997064101 523218672 483172097 719515549 37526840

样例输出 #2

374531687