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
上図はグラフ 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
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