34889번 - Promet 서브태스크다국어

Sve vrvi od različitih prometnih planova, a malog Ivicu zanima samo jedno pitanje, koliko će mu zanimljiv biti put do škole!

Možemo zamisliti da se Zagreb sastoji od $N$ kvartova označenih brojevima od $1$ do $N$. Između nekih parova kvartova $i$ te $j$ (gdje $i < j$) postoje jednaosmjerne ulice. Prometni plan sastoji se od nekog skupa takvih jednosmjernih ulica.

Ivičina kuća nalazi se u kvartu $1$, a škola u kvartu $N$. Sada ga zanima, za svaki $K$ od $0$ do $N$, koliko postoji prometnih planova, tako da broj kvartova koji se nalaze na nekom mogućem putu od kvarta $1$ do kvarta $N$ je točno $K$.

Kako su ti brojevi možda jako veliki, zanima ga njihov ostatak pri dijeljenju s $P$.

U prvom retku su prirodni brojevi $N$ i $P$.

U jedini redak ispišite $N + 1$ brojeva gdje $i$-ti broj predstavlja broj prometnih planova s $i − 1$ bitnih kvartova modulo $P$.

U svim podzadacima vrijedi $2 ≤ N ≤ 2\, 000$ i $10^8 ≤ P ≤ 10^9 + 100$, $P$ je prost broj.

Pojašnjenje drugog probnog primjera:

Vrijedi $K = 0$ za prometne planove

• $\{\}$
• $\{(1, 2)\}$
• $\{(2, 3)\}$

Vrijedi $K = 2$ za prometne planove

• $\{(1, 3)\}$
• $\{(1, 3), (1, 2)\}$ $\{(1, 3), (2, 3)\}$

Vrijedi $K = 3$ za prometne planove

• $\{(1, 2), (2, 3)\}$
• $\{(1, 2), (1, 3), (2, 3)\}$