#P18636. Junk Problem
Junk Problem
Junk Problem
给定一个有 行、 列的网格图,顶点用 表示,第 行、第 列。
通常只能沿边向下或向右行走,即从 走到 或 ,前提是目标顶点仍在网格内。
另外有 条水平边是双向边:如果 与 之间的边被指定为双向边,则也允许从 走到 。保证任意两条双向边都没有公共端点。
你需要选出 条顶点互不相交的简单路径,其中第 条从 出发,到 结束。简单路径不能重复经过同一个顶点;任意两条路径也不能经过同一个顶点。
对于这样的一组路径,如果一条双向边的两个端点都没有被任何路径访问,就称它为坏边。
求不存在坏边的路径组数量,对 取模。路径由各自经过的顶点序列区分,第 条路径的起点和终点已经指定。
注意:一条双向边只要有至少一个端点被任意路径访问,就不是坏边;并不要求路径实际经过这条边,也不要求两个端点都被访问。
输入格式
第一行四个整数 。
第二行 个整数 ,表示各条路径在第一行的起点列号。
第三行 个整数 ,表示对应路径在第 行的终点列号。
接下来 行,每行两个整数 ,表示 与 之间的边是双向边。
输出格式
输出一个整数,表示合法路径组数量对 取模的结果。
数据范围
- ;
- ,;
- ;
- ;
- ,;
- 任意两条双向边不共享端点。
输入只有一组数据。起终点的条件也隐含 。
样例输入 1
2 2 1 2
2
1
1 1
2 1
样例输出 1
2
样例输入 2
3 4 2 1
1 4
1 4
2 2
样例输出 2
0
样例输入 3
10 10 3 4
1 2 3
8 9 10
2 3
2 5
4 6
7 8
样例输出 3
388035318