A white rabbit enters a maze. The maze is a directed graph with $n$ nodes and $m$ edges, which may contain multiple edges and self-loops. The nodes are numbered from $1$ to $n$, with $S$ as the starting node and $T$ as the target node. It is guaranteed that there exists a path to $T$ from any node.
Each edge in the maze contains a monster, which is of one of two types: $0$ or $1$. The white rabbit has a score, initially $0$. Whenever the white rabbit traverses an edge:
- If the edge contains a type $1$ monster, the white rabbit kills it, gains $1$ point, and moves to the destination of the edge.
- If the edge contains a type $0$ monster, the white rabbit is stunned. The monster does not kill the rabbit, but it resets the rabbit's score to $0$ before placing the rabbit at the destination of the edge.
After traversing an edge, the monster on that edge respawns, so multiple traversals of the same edge will trigger the monster's effect each time.
Since the white rabbit does not know the structure of the maze, it decides to perform a random walk: starting from $S$, at each step, it chooses one of the outgoing edges from the current node uniformly at random, triggers the effect of the monster on that edge, and arrives at the destination. The walk ends when the white rabbit reaches $T$ for the first time.
Given the structure of the graph and the type of monster on each edge, let $X$ be the random variable representing the score when the walk ends. The white rabbit asks you to answer two questions:
- What is the expected value of $X$?
- What is the variance of $X$?
Since the white rabbit does not like real numbers, you only need to output the results modulo $998244353$. Under the given conditions, it is easy to see that the answers are rational numbers, and when expressed as irreducible fractions, the denominators are not multiples of $998244353$.
Input
The first line contains four integers $n, m, S, T$, representing the number of nodes, the number of edges, the starting node, and the target node.
The next $m$ lines each contain three integers $x, y, o$, representing a directed edge from $x$ to $y$ with a monster of type $o$.
Output
Output two integers on a single line. The first integer represents the expected value of the score, and the second integer represents the variance of the score.
Examples
Input 1
2 2 1 2 1 1 1 1 2 1
Output 1
2 2
Note 1
Starting from node $1$, there is a self-loop and an edge leading to node $2$. Each edge has $o = 1$, so the score is equal to the number of steps in the random walk.
For $x > 0$, the final score is $x$ if and only if the white rabbit traverses the self-loop at node $1$ exactly $x-1$ times and then moves to node $2$ on the $x$-th step. Therefore, the probability that the score is $x$ is $2^{-x}$. Thus, the expectation is $$\sum_{x=1}^\infty x2^{-x} = 2,$$ and the variance is $$\sum_{x=1}^{+\infty} (x-2)^2 2^{-x} = 2.$$
Constraints
For all test cases:
- $2 \le n \le 100$, $1 \le m \le n^2$;
- $1 \le S, T \le n$, $S \neq T$;
- $1 \le x, y \le n$, $0 \le o \le 1$.
- There exists a path to $T$ from any node.
Subtask 1 (4 pts): $o = 0$
Subtask 2 (24 pts): $o = 1$
Subtask 3 (8 pts): $m = n-1$, only $S$ has an in-degree of $0$, and only $T$ has an out-degree of $0$
Subtask 4 (20 pts): The given graph has no cycles
Subtask 5 (44 pts): No special restrictions
Scoring
For each test case, you receive $50\%$ of the points for that test case for each correctly answered question. The score for each subtask is the minimum of the scores of all test cases within that subtask.
Note
For a random variable $X$ taking values in the set of natural numbers, if the probability $P(X = x) = P_x$, then the expected value of $X$ is defined as $$\mathbb{E}[X] = \sum_{x = 0}^{+\infty} x P_x,$$ and the variance of $X$ is defined as $$\text{Var}[X] = \mathbb{E}[(X - \mathbb{E}[X])^2] = \sum_{x=0}^{+\infty} (x-\mathbb{E}[X])^2 P_x.$$