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)$일 때. 이는 하나의 행성 안에서 $G$의 간선을 따라 움직이는 것을 의미한다.
• $g=g'$이고 $hh'\in E(H)$일 때. 이는 행성 안에서의 위치 $g$를 그대로 유지한 채 $H$의 간선을 따라 인접한 행성으로 건너가는 것을 의미한다.

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

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

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

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

$K\ P$ $N\ M$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_M\ v_M$ $N'\ M'$ $u'_1\ v'_1\ w(u'_1, v'_1)$ $u'_2\ v'_2\ w(u'_2, v'_2)$ $\vdots$ $u'_{M'}\ v'_{M'}\ w(u'_{M'}, v'_{M'})$

$N$개의 정점과 $M$개의 간선을 가지는 그래프 $G$에 대해 정점 쌍 $(u_i, v_i)$가 주어진다는 것은 두 정점 사이에 간선이 존재함을 의미한다.

$N'$개의 정점과 $M'$개의 간선을 가지는 그래프 $H$에 대해 정점 쌍 $(u'_j, v'_j)$가 주어진다는 것은 두 정점 사이에 간선이 존재함을 의미한다. 그리고 그와 함께 주어진 $w(u'_j, v'_j)$는 해당 간선 위에 존재하는 파랑의 개수를 나타낸다.

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

• $1 \leq K \leq 100$.
• $2 \leq P \leq 10^9$.
• $P$는 소수이다.
• $\gcd(K,P)=1$.
• $2 \leq N \leq 100$.
• $1 \leq M \leq \frac{N(N-1)}{2}$.
• $1 \leq u_i < v_i \leq N$ ($1 \leq i \leq M$).
• $G$는 undirected simple connected graph.
• $2 \leq N' \leq 20$.
• $1 \leq M' \leq \frac{N'(N'-1)}{2}$.
• $1 \leq u'_j < v'_j \leq N'$ ($1 \leq j \leq M'$).
• $0 \leq w_j \leq 10^{18}$ ($1 \leq j \leq M'$).
• $H$는 undirected simple connected graph.