E. 序列配对
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

你有一个长度为 $$$n$$$ 的序列 $$$a_1,a_2,\dots,a_n$$$，初始序列内任意元素 $$$a_i=0$$$。

之后会告诉你 $$$n$$$ 组配对信息，每组配对信息形如整数对 $$$(l,r)$$$，表示将 $$$a_l$$$ 和 $$$a_r$$$ 进行配对。在配对之后，你必须执行下面两种操作之一（不可全选）：

  • 令 $$$a_l$$$ 加 $$$1$$$，随后 $$$a_r$$$ 减 $$$1$$$。
  • 令 $$$a_r$$$ 加 $$$1$$$，随后 $$$a_l$$$ 减 $$$1$$$。

你得知这些配对信息遵循着一个奇妙的规定：在 $$$n$$$ 组整数对内的 $$$2n$$$ 个整数中，每个序列的下标都恰好出现 $$$2$$$ 次！

此时你想知道，在所有操作方案中，使 $$$\sum_{i=1}^n{a_i}^2=k$$$ 的方案数，由于答案可能会很大，你只需要求出其对 $$$998\,244\,353$$$ 取模后的结果。

Input

第一行包含一个整数 $$$n\ (1\le n\le 2\cdot 10^5)$$$，表示序列的长度。

接下来 $$$n$$$ 行，其中第 $$$i$$$ 行包含两个整数 $$$l_i,r_i\ (1\le l\le r \le n)$$$，表示第 $$$i$$$ 组配对信息。保证输入的这 $$$2n$$$ 个整数符合题目要求。

最后一行包含一个整数 $$$k\ (0\le k \le 10^9)$$$，其含义如题目所述。

Output

输出一个整数，表示使 $$$\sum_{i=1}^n{a_i}^2=k$$$ 的方案数对 $$$998\,244\,353$$$ 取模后的结果。

Examples
Input
3
1 3
2 3
1 2
0
Output
2
Input
6
2 5
3 6
2 5
4 6
1 3
1 4
8
Output
28