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\).
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)\).