Biały królik wszedł do labiryntu. Labirynt jest skierowanym grafem o $n$ wierzchołkach i $m$ krawędziach, w którym mogą występować krawędzie wielokrotne oraz pętle własne. Wierzchołki są ponumerowane od $1$ do $n$, punkt startowy to $S$, a punkt końcowy to $T$. Gwarantuje się, że z każdego wierzchołka istnieje ścieżka prowadząca do $T$.
Na każdej krawędzi labiryntu znajduje się potwór jednego z dwóch typów: $0$ lub $1$. Biały królik posiada wynik, który początkowo wynosi $0$. Za każdym razem, gdy królik przechodzi przez krawędź:
- Jeśli na krawędzi znajduje się potwór typu $1$, królik pokonuje go, zdobywa $1$ punkt i przechodzi do wierzchołka końcowego tej krawędzi.
- Jeśli na krawędzi znajduje się potwór typu $0$, królik zostaje ogłuszony. Potwór nie zabija królika, ale zeruje wszystkie dotychczas zdobyte punkty, po czym królik przechodzi do wierzchołka końcowego tej krawędzi.
Po przejściu przez krawędź potwór na niej się odnawia, więc wielokrotne przechodzenie przez tę samą krawędź powoduje wielokrotne wyzwalanie efektu potwora.
Ponieważ biały królik nie zna struktury labiryntu, decyduje się na losowy spacer: startuje z $S$ i w każdym kroku z obecnego wierzchołka wybiera jedną z wychodzących krawędzi z równym prawdopodobieństwem, wyzwalając efekt potwora i przechodząc do wierzchołka końcowego. Spacer kończy się, gdy królik po raz pierwszy dotrze do $T$.
Mając daną strukturę grafu oraz typy potworów na każdej krawędzi, niech $X$ oznacza zmienną losową reprezentującą wynik w momencie zakończenia spaceru. Biały królik prosi o odpowiedź na dwa pytania:
- Jaka jest wartość oczekiwana $X$?
- Jaka jest wariancja $X$?
Ponieważ biały królik nie lubi liczb rzeczywistych, należy wypisać wyniki modulo $998244353$. Przy założeniach zadania można zauważyć, że odpowiedzi są liczbami wymiernymi, a po sprowadzeniu ich do postaci ułamka nieskracalnego, mianownik nie jest wielokrotnością $998244353$.
Wejście
Pierwsza linia wejścia zawiera cztery liczby całkowite $n, m, S, T$, oznaczające odpowiednio liczbę wierzchołków, liczbę krawędzi, punkt startowy i punkt końcowy.
Następnie $m$ linii zawiera po trzy liczby całkowite $x, y, o$, oznaczające skierowaną krawędź z $x$ do $y$ oraz typ potwora na tej krawędzi.
Wyjście
Wypisz w jednej linii dwie liczby całkowite: pierwsza to wartość oczekiwana wyniku, druga to wariancja wyniku.
Przykład
Wejście 1
2 2 1 2 1 1 1 1 2 1
Wyjście 1
2 2
Uwagi
Z wierzchołka $1$ wychodzi pętla własna oraz krawędź prowadząca do wierzchołka $2$. Każda krawędź ma $o = 1$, więc wynik jest równy liczbie kroków wykonanych podczas spaceru.
Dla $x > 0$, końcowy wynik wynosi $x$ wtedy i tylko wtedy, gdy królik najpierw wykona $x-1$ razy pętlę w wierzchołku $1$, a za $x$-tym razem przejdzie do wierzchołka $2$. Prawdopodobieństwo uzyskania wyniku $x$ wynosi zatem $2^{-x}$. Wartość oczekiwana wynosi $$\sum_{x=1}^\infty x2^{-x} = 2,$$ a wariancja wynosi $$\sum_{x=1}^{+\infty} (x-2)^2 2^{-x} = 2.$$
Podzadania
Dla wszystkich danych testowych:
- $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$.
- Z każdego wierzchołka istnieje ścieżka prowadząca do $T$.
Podzadanie 1 (4 pkt): $o = 0$
Podzadanie 2 (24 pkt): $o = 1$
Podzadanie 3 (8 pkt): $m = n-1$, w grafie tylko $S$ ma stopień wejściowy $0$, a tylko $T$ ma stopień wyjściowy $0$
Podzadanie 4 (20 pkt): Graf nie zawiera cykli
Podzadanie 5 (44 pkt): Brak dodatkowych ograniczeń
Uwagi
Dla zmiennej losowej $X$ o wartościach w zbiorze liczb naturalnych, jeśli prawdopodobieństwo $X = x$ wynosi $P_x$, to wartość oczekiwana $X$ jest zdefiniowana jako $$\mathbb{E}[X] = \sum_{x = 0}^{+\infty} x P_x,$$ a wariancja $X$ jest zdefiniowana jako $$\text{Var}[X] = \mathbb{E}[(X - \mathbb{E}[X])^2] = \sum_{x=0}^{+\infty} (x-\mathbb{E}[X])^2 P_x.$$