P15862 [LBA-OI R3 B] Go Back!

:::warning[Too abstract, view with caution] [](https://www.bilibili.com/video/BV1QxeqzfEpE/?zw&spm_id_from=888.80996.embed_old) (Fun fact: this image is **clickable**~) **Go back!** **Go back!** Walking on the wilderness road, looking at the dust and the neon lights soaring between cities in the past. Money blinds your eyes. The beginning of happiness, thinking you have a perfect ending. The busy traffic never stops. I thought I could be trapped in it too. Broken thoughts, broken wings, shattered childhood dreams — all come to lick your wounds. **Go back!** **Go back!** The crying ants melt into the mud with wine. Dust-covered memories, unchanging giving up. Broken glass hides endless sighs. Faded seasons, invisible loneliness. A suit and leather shoes are his disguise. For money, power, and dignity, he robbed my limbs. I can only shed tears and return to that home I thought was terrifying, hypocritical, unsolvable, and inhumane. **Go back!** **Go back!** :::

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$.**

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 a single integer: the result of multiplying the required probability by $n$, modulo $998244353$.

### 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$. | Subtask ID | $n$ | $k$ | Special Property | Score | |:-:|:-:|:-:|:-:|:-:| | $1$ | $\le 9$ | $\le 9$ | None | $5$ | | $2$ | Unrestricted | ^ | ^ | $10$ | | $3$ | ^ | $\le 17$ | ^ | $30$ | | $4$ | ^ | Unrestricted | A | $5$ | | $5$ | ^ | ^ | B | $5$ | | $6$ | ^ | ^ | C | $10$ | | $7$ | ^ | ^ | None | $35$ | 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