Pairing Operations and Sum of Squares

You are given a sequence of length n: \(a_1,a_2,\dots,a_n\) with all elements initially \(0\). Then, you are given n pairs \((l,r)\). It is guaranteed that in these n pairs the 2n indices (each between 1 and n) appear exactly twice. For each pair \((l,r)\), you must perform exactly one of the following two operations:

• Increase \(a_l\) by 1 and decrease \(a_r\) by 1.
• Increase \(a_r\) by 1 and decrease \(a_l\) by 1.

After you have processed all pairs (each exactly once), let the resulting sequence be \(a_1,a_2,\dots,a_n\). Define its score as \[ S=\sum_{i=1}^n a_i^2. \] You are also given an integer k. Count the number of ways to choose an operation (for each pair) so that \(S=k\). Since the answer can be very large, output it modulo \(998\,244\,353\).

Note on the structure: Because every index appears exactly twice (in one or both pairs in the role of the left element or the right element), for each index the final value will always be either \(2\), \(0\) or \(-2\) (depending on whether the two operations contribute with the same sign or cancel out). In other words, \(a_i^2\) is either \(4\) or \(0\), and hence \(S=4\,r\) where \(r\) is the number of indices in which the two operations did not cancel out. Therefore, if \(k\) is not a multiple of 4 the answer is 0. Otherwise, letting \(r=k/4\) the problem becomes counting the number of assignments so that exactly r indices become nonzero.

A careful analysis (by grouping the indices into cycles induced by the given pairs) shows that each cycle (of length \(L\)) contributes a polynomial \[ P_{cycle}(z)=\sum_{r=0}^{L} \Bigl[2\binom{L}{r}\text{ if } (-1)^{L-r}=\Delta \Bigr] z^r, \] where \(\Delta\in\{1,-1\}\) is determined by the fixed positions of each index in its two occurrences (namely, if an index appears twice with the same sign then it contributes a factor \(1\), otherwise \(-1\)). The final answer is the coefficient of \(z^{k/4}\) when multiplying together the polynomials from all cycles.

inputFormat

The first line contains two integers \(n\) and \(k\) \( (1 \le n \le N,\; 0\le k \le \text{some bound})\). Here n is the length of the sequence and also the number of pairs, and k is the target sum of squares.

Then \(n\) lines follow. The i-th of these lines contains two integers \(l_i\) and \(r_i\) \( (1 \le l_i, r_i \le n)\) indicating a pair. It is guaranteed that every index in \(\{1,2,\dots,n\}\) appears exactly twice in total among these \(2n\) numbers.

outputFormat

Output one integer, the number of valid operation assignments that yield \(\sum_{i=1}^n a_i^2=k\), modulo \(998\,244\,353\).

sample

2 4
1 2
1 2

0