#P9773. [HUSTFC 2023] 序列配对

[HUSTFC 2023] 序列配对

题目描述

你有一个长度为 nn 的序列 a1,a2,,ana_1,a_2,\dots,a_n,初始序列内任意元素 ai=0a_i=0

之后会告诉你 nn 组配对信息,每组配对信息形如整数对 (l,r)(l,r),表示将 ala_lara_r 进行配对。在配对之后,你必须执行下面两种操作之一(不可全选):

  • ala_l11,随后 ara_r11
  • ara_r11,随后 ala_l11

你得知这些配对信息遵循着一个奇妙的规定:在 nn 组整数对内的 2n2n 个整数中,每个序列的下标都恰好出现 22 次!

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

输入格式

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

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

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

输出格式

输出一个整数,表示使 i=1nai2=k\sum_{i=1}^n{a_i}^2=k 的方案数对 998244353998\,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