AT_abc372_f [ABC372F] Teleporting Takahashi 2

[problemUrl]: https://atcoder.jp/contests/abc372/tasks/abc372_f $ 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 $ で割った余りを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_M $ $ Y_M $

答えを $ 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 $ 本の有向辺はすべて異なる - 入力は全て整数 ### Sample Explanation 1 !\[sample1\](https://img.atcoder.jp/abc372/7a174918a45bdbdfb3457d9c62bea943.png) 上図はグラフ $ 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 $