Mała Y jest dziewczynką o bujnej wyobraźni.
Pewnej nocy, patrząc na rozgwieżdżone niebo, zaczęła rozpoznawać gwiazdozbiory, korzystając ze zdobytej wcześniej wiedzy astronomicznej. Tym razem jednak chciała dodać do dokonań swoich poprzedników własne pomysły, aby stworzyć wzory, które będą jej własnymi.
Na niebie znajduje się łącznie $n$ gwiazd. Przeglądając różne starożytne i współczesne księgi, mała Y zebrała $m$ fragmentów informacji. Każdy $i$-ty fragment mówi, że między gwiazdą $a_i$ a gwiazdą $b_i$ powinno istnieć połączenie. Dla każdego fragmentu mała Y, biorąc pod uwagę jego wiek, pochodzenie i inne informacje, przypisała temu połączeniu wagę $c_i$.
Mała Y chce wybrać niektóre z tych $m$ fragmentów informacji i połączyć gwiazdy zgodnie z nimi, tworząc swój własny wzór.
Mała Y chce, aby uzyskany wzór nie zawierał wielokrotnych krawędzi, co oznacza, że między dowolnymi dwiema gwiazdami może istnieć co najwyżej jedna krawędź. Ponadto wzór ten musi być spójny.
Co więcej, ponieważ mamy rok 2017, mała Y chce, aby suma wag wybranych przez nią krawędzi modulo $p = 17$ była równa określonej liczbie. Mała Y chce wiedzieć, dla każdego $k$ z zakresu $0 \le k < p$, ile jest sposobów na stworzenie spójnego wzoru bez wielokrotnych krawędzi, w którym suma wag krawędzi modulo $p$ wynosi $k$.
Ponieważ wynik może być bardzo duży, wystarczy podać go modulo $998244353$.
Wejście
Pierwsza linia zawiera dwie liczby całkowite $n, m$, których znaczenie opisano powyżej.
Następnie $m$ linii, każda zawiera trzy liczby całkowite $a_i, b_i, c_i$, oznaczające krawędź łączącą $a_i$ i $b_i$ o wadze $c_i$.
Wyjście
Wypisz $p$ linii, w każdej jedna liczba całkowita. $i$-ta linia powinna zawierać liczbę sposobów, dla których suma wag krawędzi modulo $p$ wynosi $i - 1$, obliczoną modulo $998244353$.
Przykład
Przykład 1
4 8 1 2 0 1 2 1 2 3 0 2 3 1 3 4 0 3 4 1 1 4 0 1 4 2
Wyjście 1
5 12 13 11 6 1 0 0 0 0 0 0 0 0 0 0 0
Podzadania
Skala danych i charakterystyka każdego punktu testowego zostały przedstawione w poniższej tabeli.
| Punkt testowy | $n$ | $m$ | Inne ustalenia |
|---|---|---|---|
| 1 | $\leq17$ | $\leq20$ | Brak |
| 2 | $\leq25$ | ||
| 3 | $\leq30$ | ||
| 4 | $\leq10^5$ | Wagi wynoszą $0$ | |
| 5 | |||
| 6 | $\leq14$ | $\leq50$ | Wagi wynoszą $1$ |
| 7 | |||
| 8 | $\leq15$ | ||
| 9 | |||
| 10 | |||
| 11 | $\leq13$ | $\leq10^5$ | Brak |
| 12 | $\leq14$ | ||
| 13 | |||
| 14 | $\leq15$ | ||
| 15 | |||
| 16 | $\leq16$ | ||
| 17 | |||
| 18 | |||
| 19 | |||
| 20 | $\leq17$ | ||
| 21 | |||
| 22 | |||
| 23 | |||
| 24 | |||
| 25 |
Dla 100% danych zapewnione jest $1 \le n \le 17, 1 \le m \le 10^5, 0 \le c_i < p = 17$.