409341: GYM103486 H Visit the Park

Little Msacywy is visiting a beautiful park! The park has $$$N$$$ scenic spots, and there are $$$M$$$ bidirectional roads between them. In other words, the park can be considered as an undirected graph.

Before his visit, Msacywy had already planned his visiting path. The path is a sequence of scenic spots $$$\{A_1, A_2, \ldots A_K\}$$$. He will start at spot $$$A_1$$$, and go strictly along the path, which means when he is at spot $$$A_i$$$, he will find a road between $$$A_i$$$ and $$$A_{i+1}$$$ and move to $$$A_{i+1}$$$ with this road. If there are several roads between $$$A_i$$$ and $$$A_{i+1}$$$, he will choose a road randomly with equal probability. Note that Msacywy can reach a spot more than once.

Moreover, each road has a digit between $$$1$$$ and $$$9$$$. When Msacywy passes through the $$$i$$$-th road, he will write down the digit of this road from left to right on his paper. Finally, there will be an integer of $$$k - 1$$$ digits on his paper.

Given the structure of the park and the planned path of Msacywy. Find the expected number of the integer written on the paper. We can show that the answer can be written in the form $$$\frac{A}{B}$$$ where $$$A, B$$$ are relatively prime numbers. Output the value of $$$A \times B^{-1}$$$ modulo $$$\mathbf{998244853}$$$.

The first line of input file contains three integers $$$N, M$$$ and $$$K (2 \le N, M, K \le 3 \times 10^5)$$$, indicating the number of spots, the number of roads and the length of planned path.

The following $$$M$$$ lines describe all the roads. Each line contains three integers $$$u, v (1 \le u, v \le N, u \neq v)$$$ and $$$w (1 \le w \le 9)$$$, representing a road between $$$u$$$ and $$$v$$$ with digit $$$w$$$.

The last line contains $$$K$$$ integers $$$A_1, A_2, \ldots A_K (1 \le A_i \le N, A_i \neq A_{i+1})$$$, representing the planned path of Msacywy.

If Msacywy can go along the path, output a single integer, the expected number modulo $$$\mathbf{998244853}$$$; otherwise, output a line "Stupid Msacywy!" (without quotes).

3 5 3
1 2 1
1 2 2
2 1 2
2 3 4
3 2 1
1 2 3

831870730

3 3 5
1 2 1
2 3 4
3 2 1
1 2 3 2 3

499123704

3 4 4
1 2 1
1 2 2
2 1 3
2 3 5
1 2 3 1

Stupid Msacywy!

For the first sample, the integer could be $$$4$$$ different values:

• $$$14$$$ with probability $$$\frac{1}{6}$$$;
• $$$11$$$ with probability $$$\frac{1}{6}$$$;
• $$$24$$$ with probability $$$\frac{1}{3}$$$;
• $$$21$$$ with probability $$$\frac{1}{3}$$$.

So the answer is $$$14 \times \frac{1}{6} + 11 \times \frac{1}{6} + 24 \times \frac{1}{3} + 21 \times \frac{1}{3} = \frac{115}{6}$$$.