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의 가중치 합의 기댓값을 $998244353$으로 나눈 나머지를 구하시오.

중복간선이 있을 수 있음에 주의하라.

$1 \leq N, M, K \leq 10^5 \\ 1 \leq a_i < b_i \leq N$ 기존 $DAG$에서 1번 정점에서 다른 모든 정점에 도달할 수 있음을 보장한다.

첫 줄에 $N$, $M$, $K$가 주어진다. 그 후 $M$개의 줄에 걸쳐서 $i+1$번째 줄에 간선을 뜻하는 $a_i \; b_i$ $(a_i < b_i)$가 주어진다. 이는 $a_i$에서 $b_i$로 가는 유향 간선이 존재함을 뜻한다.

기댓값을 $998244353$으로 나눈 나머지를 출력한다.

서브태스크

1. $M = N-1$ (5점)

2. $M \le 10, K \le 2$ (11점)

3. $N, M, K \le 1\,000$ (37점)

4. 추가적인 제한 조건 없음 (47점)