Extradimensional Cosmic Phenomenon

That Light... It's there, blue, and far away... ...and yet, she finds it as beautiful as ever.

모든 '행성'은 그래프 $G$와 동일한 구조를 가진다. 각 행성은 그래프 $H$의 한 정점에 대응되며, 두 행성 사이의 인접 여부는 $H$에서의 인접 여부로 정해진다. 이들 행성과 그 사이를 연결하는 길들이 이루는 전체 그래프를 '우주'라고 부르자.

보다 엄밀히, 우주 전체의 정점 집합 $V(G)\times V(H)$ 내 임의의 두 정점 $(g,h)$와 $(g',h')$은 다음의 조건 중 하나를 만족할 때, 그리고 그때에만 간선으로 연결된다.

• $h=h'$이고 $gg'\in E(G)$일 때. 이는 하나의 행성 안에서 $$의 간선을 따라 움직이는 것을 의미한다.

뛰어난 러너 노노카(ノノカ)는 온 우주의 정점들을 하나의 스패닝 트리로 연결하고자 마음먹는다. 그 전에 우주의 규모를 우선 파악해 보고 싶었던 노노카는, 스패닝 트리를 그리는 방법의 수를 트리가 포함하는 파랑의 개수에 따라 구분하여 세어 보기로 한다. $H$에서 인접한 두 행성 $u$, $v$를 연결하는 각각의 간선 위에는 $w(u,v)$개의 파랑이 존재하며, 이때 $n$개의 을 포함하는 스패닝 트리의 수를 으로 정의하자. 이와 같은 방식으로 노노카는 수열 를 구성할 수 있다.

그러나 수열 $\{A_n\}$이 길어지는 것이 싫었던 노노카는 $K$개 이상의 파랑이 모이면 그 자리에서 $K$개씩 날려보내기로 한다! 그렇게 길이 $K$로 압축된 수열을 $\{B_k\}$라 하자. (즉, 에 대해 로 정의된다.)

우주를 항해하는 노노카를 도와 수열 $\{B_k\}: B_0,B_1,\cdots,B_{K-1}$를 계산해주자! (단, 각 항의 크기가 너무 커질 수 있으니 소수 로 나눈 나머지를 출력한다.)

입력은 다음과 같은 형식으로 주어진다.

$K\ P$ $N\ M$ $u_1\ v_1$

첫째 줄에 $B_0,B_1,\ldots,B_{K-1}$를 소수 로 나눈 나머지를 공백으로 구분하여 출력한다.

• $1 \leq K \leq 100$.
• $2 \leq P \leq 10^9$.
• 는 소수이다.