Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

graphs

math

matrices

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. European Trip

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe map of Europe can be represented by a set of $$$n$$$ cities, numbered from $$$1$$$ through $$$n$$$, which are connected by $$$m$$$ bidirectional roads, each of which connects two distinct cities. A trip of length $$$k$$$ is a sequence of $$$k+1$$$ cities $$$v_1, v_2, \ldots, v_{k+1}$$$ such that there is a road connecting each consecutive pair $$$v_i$$$, $$$v_{i+1}$$$ of cities, for all $$$1 \le i \le k$$$. A special trip is a trip that does not use the same road twice in a row, i.e., a sequence of $$$k+1$$$ cities $$$v_1, v_2, \ldots, v_{k+1}$$$ such that it forms a trip and $$$v_i \neq v_{i + 2}$$$, for all $$$1 \le i \le k - 1$$$.

Given an integer $$$k$$$, compute the number of distinct special trips of length $$$k$$$ which begin and end in the same city. Since the answer might be large, give the answer modulo $$$998\,244\,353$$$.

Input

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$3 \le n \le 100$$$, $$$1 \le m \le n(n - 1) / 2$$$, $$$1 \le k \le 10^4$$$) — the number of cities, the number of roads and the length of trips to consider.

Each of the following $$$m$$$ lines contains a pair of distinct integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le n$$$) — each pair represents a road connecting cities $$$a$$$ and $$$b$$$. It is guaranteed that the roads are distinct (i.e., each pair of cities is connected by at most one road).

Output

Print the number of special trips of length $$$k$$$ which begin and end in the same city, modulo $$$998\,244\,353$$$.

Examples

Input

4 5 2 4 1 2 3 3 1 4 3 2 4

Output

0

Input

4 5 3 1 3 4 2 4 1 2 1 3 4

Output

12

Input

8 20 12 4 3 6 7 5 7 8 2 8 3 3 1 4 7 8 5 5 4 3 5 7 1 5 1 7 8 3 2 4 2 5 2 1 4 4 8 3 6 4 6

Output

35551130

Note

In the first sample, we are looking for special trips of length $$$2$$$, but since we cannot use the same road twice once we step away from a city we cannot go back, so the answer is $$$0$$$.

In the second sample, we have the following $$$12$$$ special trips of length $$$3$$$ which begin and end in the same city: $$$(1, 2, 4, 1)$$$, $$$(1, 3, 4, 1)$$$, $$$(1, 4, 2, 1)$$$, $$$(1, 4, 3, 1)$$$, $$$(2, 1, 4, 2)$$$, $$$(2, 4, 1, 2)$$$, $$$(3, 1, 4, 3)$$$, $$$(3, 4, 1, 3)$$$, $$$(4, 1, 3, 4)$$$, $$$(4, 3, 1, 4)$$$, $$$(4, 1, 2, 4)$$$, and $$$(4, 2, 1, 4)$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/19/2024 18:03:11 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|