The Republic of AtCoder has $N$ cities, called City $1$, City $2$, ……, City $N$. Initially, there was a bidirectional road between every pair of different cities, but $M$ of these roads have become unusable due to deterioration over time. More specifically, for each $1≤i≤M$, the road connecting City $U_i$ and City $V_i$ has become unusable.
Takahashi will go for a $K$-day trip that starts and ends in City $1$. Formally speaking, a $K$-day trip that starts and ends in City $1$ is a sequence of $K+1$ cities $(A_0,\ A_1,\ …,\ A_K)$ such that $A_0=A_K=1$ holds and for each $0≤i≤K−1$, $A_i$ and $A_{i+1}$ are different and there is still a usable road connecting City $A_i$ and City $A_{i+1}$.
Print the number of different $K$-day trips that start and end in City $1$, modulo $998244353$. Here, two $K$-day trips $(A_0,\ A_1,\ …,\ A_K)$ and $(B_0,\ B_1,\ …,\ B_K)$ are said to be different when there exists an $i$ such that $A_i≠B_i$.

Input is given from Standard Input in the following format:
$N\ M\ K$
$U_1\ V_1$
$:$
$U_M\ V_M$

Print the answer.

$2≤N≤5,000$
$0≤M≤min(\frac{N}{(N−1)},\ 5,000)$
$2≤K≤5,000$
$1≤U_i<V_i≤N$
All pairs $(U_i,\ V_i)$ are pairwise distinct.
All values in input are integers.

4

There are four different trips as follows.

• (1,2,1,2,11,2,1,2,1)
• (1,2,1,3,11,2,1,3,1)
• (1,3,1,2,11,3,1,2,1)
• (1,3,1,3,11,3,1,3,1)

No other trip is valid, so we should print 44.

0

No road remains usable, so there is no valid trip.