Problem Statement

You are given a rooted tree with $N$ vertices numbered $1$ through $N$. Vertex $1$ is the root, and the parent of vertex $i$ is vertex $p_i$ ($p_i \lt i$). Each vertex is colored: vertex $i$ is colored with color $c_i$ ($1 \leq c_i \leq N$). For each $v = 1, 2, \dots, N$, solve the following problem:

Let $f_i$ be the number of vertices colored with color $i$ among the vertices in the subtree rooted at vertex $v$.

Find:

• the maximum value $m$ among the values in the sequence $(f_1, f_2, \dots, f_N)$, and
• the number $k$ of positive integers $i$ not greater than $N$ such that $f_i = m$.

Input/Output Format

The input and output for this problem follow a special format.

Input Format

From Standard Input, you are given the integer $N$ along with integers $\mathrm{seed}, M, F$ and $q_2, q_3, \dots, q_M$, $d_1, d_2, \dots, d_M$. Reconstruct $p_2, p_3, \dots, p_N$ and $c_1, c_2, \dots, c_N$ using the computation described by the following pseudocode. (Here, 2^31 means $2^{31}=2147483648$. Note that $\mathrm{state}$ is a variable, and that a $64$-bit integer type is required for computing $\mathrm{state}$.)

state = seed

for i=2 to N:
  if i <= M:
    p[i] = q[i]
  else:
    p[i] = (state mod (i-1)) + 1
    state = (state * 1103515245 + 12345) mod 2^31

for i=1 to N:
  if i <= M:
    c[i] = d[i]
  else:
    c[i] = (state mod F) + 1
    state = (state * 1103515245 + 12345) mod 2^31

Output Format

Let $m_i$ and $k_i$ denote $m$ and $k$ when $v=i$, respectively. Output this value:

$\left(\displaystyle \sum_{i=1}^N (m_i \oplus i)\times (k_i \oplus i)\right) \bmod 998244353$

Here, $\oplus$ denotes bitwise XOR. Beware of overflow during computation.

Constraints

• $2 \leq N \leq 2.5 \times 10^6$
• $1 \leq p_i \lt i$
• $1 \leq c_i \leq N$
• $1 \leq \mathrm{seed} \lt 2^{31}$
• $2 \leq M \leq \min(N, 10^5)$
• $1 \leq F \leq N$
• $1 \leq q_i \lt i$
• $1 \leq d_i \leq N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N \mathrm{seed} M F
q_2 q_3 \dots q_M
d_1 d_2 \dots d_M

Output

Output $\left(\displaystyle \sum_{i=1}^N (m_i \oplus i)\times (k_i \oplus i)\right) \bmod 998244353$.