問題文

頂点 $1,2,\dots,N$ からなる無向完全グラフ^† があります。
このグラフから ちょうど $M$ 本 の辺を取り除いて、新しい無向グラフ $G$ を作ります。
残ったグラフ $G$ における頂点 $1$ から頂点 $N$ への最短距離（通る辺の本数）を、ちょうど $K$ にしたいです^‡。

この条件を満たすような辺の取り除き方の個数を $998244353$ で割った余りを求めてください。
なお、取り除く辺の集合が異なれば、別の取り除き方とみなします。

^† 「無向完全グラフ」とは、相異なる任意の $2$ 頂点の間にちょうど $1$ 本の辺が存在する、自己ループや多重辺のない無向グラフのことを指します。
^‡ ただし、頂点 $1$ から頂点 $N$ へ到達できない場合は、条件を満たさないものとします。

制約

• $2 \leq N \leq {\mathbf{35}}$
• $0 \leq M \leq \dfrac{N(N-1)}{2}$
• $1 \leq K \leq N-1$
• 入力はすべて整数

入力

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

$N\ M\ K$

出力

答えを $998244353$ で割った余りを 1 行で出力してください。

サンプル

4 2 2

5

5 5 4

0

35 520 25

843751679