F - Teleporting Takahashi 2 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 525

問題文

N 頂点 N+M 辺の単純有向グラフ G があります。頂点には 1 から N の番号が、辺には 1 から N+M までの番号がつけられています。

i (1 \leq i \leq N) は頂点 i から頂点 i+1 へ張られています。(ただし、頂点 N+1 は頂点 1 とみなします。)
N+i\ (1\leq i\leq M) は頂点 X_i から頂点 Y_i へ張られています。

高橋君は頂点 1 にいます。各頂点において、高橋君はその頂点から有向辺が張られている頂点に移動することができます。

高橋君がちょうど K 回移動する方法が何通りあるかを求めてください。

すなわち、長さ K+1 の 整数列 (v_0,v_1,\dots,v_K) であって、下記の 3 つの条件をすべて満たすものの個数を求めてください。

  • i=0,1,\dots,K について、1\leq v_i\leq N
  • v_0=1
  • i=1,2,\ldots,K について、頂点 v_{i-1} から頂点 v_i へ有向辺が張られている。

ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを出力してください。

制約

  • 2\leq N\leq 2\times 10^5
  • 0\leq M\leq 50
  • 1\leq K\leq 2\times 10^5
  • 1\leq X_i,Y_i\leq N,X_i\neq Y_i
  • N+M 本の有向辺はすべて異なる
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M K
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

出力

答えを 998244353 で割った余りを出力せよ。


入力例 1

6 2 5
1 4
2 5

出力例 1

5

sample1

上図はグラフ G を表しています。以下の 5 通りの移動方法が存在します。

  • 頂点 1\to 頂点 2\to 頂点 3\to 頂点 4\to 頂点 5\to 頂点 6
  • 頂点 1\to 頂点 2\to 頂点 5\to 頂点 6\to 頂点 1\to 頂点 2
  • 頂点 1\to 頂点 2\to 頂点 5\to 頂点 6\to 頂点 1\to 頂点 4
  • 頂点 1\to 頂点 4\to 頂点 5\to 頂点 6\to 頂点 1\to 頂点 2
  • 頂点 1\to 頂点 4\to 頂点 5\to 頂点 6\to 頂点 1\to 頂点 4

入力例 2

10 0 200000

出力例 2

1

入力例 3

199 10 1326
122 39
142 49
164 119
197 127
188 145
69 80
6 120
24 160
18 154
185 27

出力例 3

451022766

Score : 525 points

Problem Statement

There is a simple directed graph G with N vertices and N+M edges. The vertices are numbered 1 to N, and the edges are numbered 1 to N+M.

Edge i (1 \leq i \leq N) goes from vertex i to vertex i+1. (Here, vertex N+1 is considered as vertex 1.)
Edge N+i (1 \leq i \leq M) goes from vertex X_i to vertex Y_i.

Takahashi is at vertex 1. At each vertex, he can move to any vertex to which there is an outgoing edge from the current vertex.

Compute the number of ways he can move exactly K times.

That is, find the number of integer sequences (v_0, v_1, \dots, v_K) of length K+1 satisfying all of the following three conditions:

  • 1 \leq v_i \leq N for i = 0, 1, \dots, K.
  • v_0 = 1.
  • There is a directed edge from vertex v_{i-1} to vertex v_i for i = 1, 2, \ldots, K.

Since this number can be very large, print it modulo 998244353.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 50
  • 1 \leq K \leq 2 \times 10^5
  • 1 \leq X_i, Y_i \leq N, X_i \neq Y_i
  • All of the N+M directed edges are distinct.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M K
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

Output

Print the count modulo 998244353.


Sample Input 1

6 2 5
1 4
2 5

Sample Output 1

5

sample1

The above figure represents the graph G. There are five ways for Takahashi to move:

  • Vertex 1 \to Vertex 2 \to Vertex 3 \to Vertex 4 \to Vertex 5 \to Vertex 6
  • Vertex 1 \to Vertex 2 \to Vertex 5 \to Vertex 6 \to Vertex 1 \to Vertex 2
  • Vertex 1 \to Vertex 2 \to Vertex 5 \to Vertex 6 \to Vertex 1 \to Vertex 4
  • Vertex 1 \to Vertex 4 \to Vertex 5 \to Vertex 6 \to Vertex 1 \to Vertex 2
  • Vertex 1 \to Vertex 4 \to Vertex 5 \to Vertex 6 \to Vertex 1 \to Vertex 4

Sample Input 2

10 0 200000

Sample Output 2

1

Sample Input 3

199 10 1326
122 39
142 49
164 119
197 127
188 145
69 80
6 120
24 160
18 154
185 27

Sample Output 3

451022766