Problem Description

You have a sequence of length $n$: $a_1,a_2,\dots,a_n$. Initially, every element in the sequence satisfies $a_i=0$.

Then you are given $n$ pairs of indices. Each pair is an integer pair $(l,r)$, meaning that $a_l$ and $a_r$ are paired. After each pairing, you must perform exactly one of the following two operations (you cannot do both):

• Increase $a_l$ by $1$, then decrease $a_r$ by $1$.
• Increase $a_r$ by $1$, then decrease $a_l$ by $1$.

You are also told that these pairings follow a special rule: among the $2n$ integers appearing in the $n$ pairs, each index of the sequence appears exactly $2$ times.

You want to know, among all possible choices of operations, how many result in $\sum_{i=1}^n a_i^2 = k$. Since the answer may be very large, output it modulo $998\,244\,353$.

Input Format

The first line contains an integer $n\ (1\le n\le 2\cdot 10^5)$, the length of the sequence.

The next $n$ lines each contain two integers $l_i,r_i\ (1\le l\le r \le n)$, describing the $i$-th pairing. It is guaranteed that these $2n$ integers satisfy the requirement in the statement.

The last line contains an integer $k\ (0\le k \le 10^9)$, with the meaning as described above.

Output Format

Output one integer: the number of operation plans such that $\sum_{i=1}^n a_i^2=k$, modulo $998\,244\,353$.

3
1 3
2 3
1 2
0

2

6
2 5
3 6
2 5
4 6
1 3
1 4
8

28

Hint

Translated by ChatGPT 5