Narciarz Zbyszek

Narciarz Zbyszek spędza ferie zimowe w kurorcie narciarskim. W okolicy kurortu jest n polanek, niektóre polanki połączone sa nartostradami. Polanki są ponumerowane liczbami od 1 do n, przy czym polanka o mniejszym numerze leży wyżej, czyli nartostrada może prowadzić tylko z polanki o mniejszym numerze do polanki o większym numerze.

Zbyszek zastanawia się, na ile sposobów może on zjeżdzać na nartach. Dla każdej pary polan (a, b) wypisz, na ile sposobów może on pojechać z polany a do polany b używając danych nartostrad. Dla par (a, a) wypisz 0.

Wejście

W pierwszym wierszu wejścia jest liczba 2 <= n <= 100. Kolejne n wierszy zawiera po n liczb 0 lub 1; j-ta liczba w i-tym wierszu oznacza, czy istnieje nartostrada z polany i do polany j - 1 jeśli istnieje, 0 jeśli nie istnieje. Dla i>=j zawsze będzie to 0.

Wyjście

Wypisz n rzędów po n liczb w każdym; j-ta liczba w i-tym wierszu powinna być liczbie sposobów dotarcia z polany i do polany j, (!!!) modulo 123456789 (!!!) (czyli resztę z dzielenia przez 123456789). Dla i>=j należy wypisać 0.

Przykład

Dla wejścia:

5
0 1 1 1 1
0 0 0 1 1
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0

prawidłowym rozwiązaniem jest:

0 1 1 3 6
0 0 0 1 2
0 0 0 1 2
0 0 0 0 1
0 0 0 0 0