Description

We have a directed graph $G$ with $n$ nodes and $n$ edges, where each node has out-degree exactly $1$. Each node is assigned a lowercase letter as its weight.

DZ1000 is about to walk on $G$. He uses a string $s$ and a stack $t$ to record his journey. Initially, the stack $t$ is empty.

In each step, he has two choices of action:

1. Move forward: With probability $p$, he moves along the outgoing edge of the current node and pushes the reached node into stack $t$.
2. Go back: With probability $(1-p)$, he pops the top node from stack $t$ and returns to the node that is now the top of stack $t$. (If stack $t$ is empty before this action, he cannot do this and must move forward; if the size of stack $t$ is $1$ before this action, he returns to the starting node.)

Immediately after each step, DZ1000 appends the weight of the current node to the string $s$.

DZ1000 randomly selects a starting node on $G$ with equal probability, then takes exactly $2k$ steps. You need to find the probability that the first $k$ characters of $s$ are equal to the last $k$ characters after $2k$ steps. Multiply the answer by $n$ and take it modulo $998244353$.

Note: The weight of the starting node is NOT the first character of string $s$.

Input Format

The input contains exactly $3$ lines.

The first line has three positive integers $n, k, p$, representing the number of nodes in $G$, the number of steps taken, and the probability of moving forward (originally a rational number between $0$ and $1$, given modulo $998244353$).

The second line is a string of lowercase letters with length $n$. The $i$-th letter $c_i$ is the weight of node $i$.

The third line has $n$ positive integers $v$. The $i$-th integer $v_i$ is the node that the outgoing edge of node $i$ points to.

Output Format

Output a single integer: the result of multiplying the required probability by $n$, modulo $998244353$.

3 1 499122177
aba
2 3 1

1

10 10 882315098
nqqmlmnnon
6 3 4 1 4 4 9 4 10 7 

106458929

Hint

Explanation of Sample 1

$\frac{1}{2}$ modulo $998244353$ is $499122177$, so the original $p = \frac{1}{2}$.

The paths are as follows:

• $1\to 2\to 3$, probability $\frac{1}{n}\times p=\frac{1}{6}$, string ba — invalid
• $1\to 2\to 1$, probability $\frac{1}{n}\times p=\frac{1}{6}$, string ba — invalid
• $2\to 3\to 1$, probability $\frac{1}{n}\times p=\frac{1}{6}$, string aa — valid
• $2\to 3\to 2$, probability $\frac{1}{n}\times p=\frac{1}{6}$, string ab — invalid
• $3\to 1\to 2$, probability $\frac{1}{n}\times p=\frac{1}{6}$, string ab — invalid
• $3\to 1\to 3$, probability $\frac{1}{n}\times p=\frac{1}{6}$, string aa — valid

Total valid probability: $\frac{1}{6}+\frac{1}{6}=\frac{1}{3}$. Multiply by $n$ to get $1$, so output $1$.

Data Constraints

For $100\%$ data: $1 \le n \le 30,\ 1 \le k \le 30$.

Special Property A: All $c_i$ are identical.

Special Property B: For all $1\le i\le n$, $v_i=i$.

Special Property C: For all $1\le i<n$, $v_i=i+1$, and $v_n=1$.