European Trip

2000ms

262144K

Description:

The 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$$$.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample 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)$$$.

Informação

Provedor Codeforces

Código CF1662C