#P18191. Two Box
Two Box
Two Box
给定长度为 的整数序列 ,以及 次修改。第 次修改将 改为 ,然后对修改后的序列回答下面的计数问题。各次对序列的修改会保留。
有一个白盒、一个黑盒,以及编号为 的 个球。开始时所有球都在白盒中。
需要恰好执行 次操作。每次选择一个编号 ,,把球 从当前的盒子移到另一个盒子。
要求:在第 次操作完成后,黑盒中所有球的编号都不超过 。黑盒为空时自然满足这一条件。
求满足全部条件的操作序列数量,对 取模。操作序列由每次选择的球编号确定。
请依次回答每次修改后的结果。每次计数都假设从“所有球都在白盒”重新开始;这里只对 累积修改,不在询问之间保留某次操作实验的球状态。最后一次操作结束时不要求黑盒为空。
输入格式
第一行三个整数 。
第二行 个整数 。
接下来 行,第 行两个整数 ,表示将 修改为 。
输出格式
输出 行,第 行一个整数,表示第 次修改后满足条件的操作序列数量对 取模的结果。不输出修改前的答案。
数据范围
- ;
- ;
- ;
- 。
样例 1 输入
3 3 2
1 3 1
3 2
1 3
样例 1 输出
5
14
样例 2 输入
6 8 1
3 8 7 7 1 6
1 4
样例 2 输出
2100
样例 3 输入
12 10 8
1 3 2 6 3 6 7 7 5 5 4 7
12 4
7 10
4 2
9 8
9 9
8 3
4 9
10 2
样例 3 输出
2741280
3007680
1503840
1916160
1972800
728640
1821600
621440
样例说明
样例 1 第一次修改后 ,合法的选球序列恰好是
$$(1,1,1),\quad(1,1,2),\quad(1,2,1),\quad(1,2,2),\quad(1,3,3).$$例如 :先把球 移入黑盒,再把球 移入黑盒,最后把球 移回白盒,黑盒中只剩球 ,分别满足三个时刻的限制。
第二次修改是在第一次修改后的序列上进行,得到 ,答案为 。