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.
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.
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.
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
[Zgłoś rozwiązanie] [Moje zgłoszenia]