MST on DAG

정점 $N$개, 유향 간선 $M$개로 이루어진 $DAG$가 주어진다. 위에서의 spanning tree란 다음을 뜻한다.

• 간선의 방향을 제거했을 때, 이는 spanning tree가 된다.
• 1번 정점을 루트로 하는 트리로 생각했을 때, 모든 간선은 부모에서 자식 방향으로 향한다. 즉, 1번 정점에서 다른 모든 정점에 도달할 수 있다.

각 간선에 가중치가 부여되었을 때, 위에서의 minimum spanning tree란 다음과 같다.

• $DAG$위에서의 spanning tree이다.
• 가능한 spanning tree중, 사용된 간선의 가중치 합이 최소가 되는 것이다. 여러개 존재한다면 그것들 모두 minimum spanning tree이다.

$M$개의 간선에 각각 $1$이상 $K$이하의 가중치를 붙이는 $K^M$가지의 경우에 대해, minimum spanning tree의 가중치 합의 기댓값을 $998\ 244\ 353$으로 나눈 나머지를 구하시오.

중복간선이 있을 수 있음에 주의하라. 기존 $DAG$에서 1번 정점에서 다른 모든 정점에 도달할 수 있음을 보장한다.

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

$N\ M\ K$ $a_1\ b_1$ $a_2\ b_2$ $\vdots$ $a_M\ b_M$

이는 $a_i$에서 $b_i$로 가는 유향 간선이 존재함을 뜻한다. $(1\le i\le M)$

기댓값을 $998\ 244\ 353$으로 나눈 나머지를 출력한다.

• $1 \leq N, M, K \leq 10^5$.
• $1 \leq a_i < b_i \leq N$.