#P9773. [HUSTFC 2023] 序列配对
[HUSTFC 2023] 序列配对
题目描述
你有一个长度为 的序列 ,初始序列内任意元素 。
之后会告诉你 组配对信息,每组配对信息形如整数对 ,表示将 和 进行配对。在配对之后,你必须执行下面两种操作之一(不可全选):
- 令 加 ,随后 减 。
- 令 加 ,随后 减 。
你得知这些配对信息遵循着一个奇妙的规定:在 组整数对内的 个整数中,每个序列的下标都恰好出现 次!
此时你想知道,在所有操作方案中,使 的方案数,由于答案可能会很大,你只需要求出其对 取模后的结果。
输入格式
第一行包含一个整数 ,表示序列的长度。
接下来 行,其中第 行包含两个整数 ,表示第 组配对信息。保证输入的这 个整数符合题目要求。
最后一行包含一个整数 ,其含义如题目所述。
输出格式
输出一个整数,表示使 的方案数对 取模后的结果。
3
1 3
2 3
1 2
0
2
6
2 5
3 6
2 5
4 6
1 3
1 4
8
28