#P18564. Not Another Constructive Problem

Not Another Constructive Problem

Not Another Constructive Problem

考虑一棵有 nn 个顶点的树 T=(V,E)T=(V,E),顶点编号为 1,2,…,n1,2,\ldots,n。顶点 ii 最初放着数值 pip_i,其中 pp 是 11 到 nn 的一个排列。

你需要执行以下操作恰好 n−1n-1 次:

  1. 选择一条仍在 EE 中的边 e=(x,y)e=(x,y)。
  2. 交换顶点 x,yx,y 上的数值,即交换 px,pyp_x,p_y。
  3. 从 EE 中删除这条边。

最后,树的所有边都会被删除。如果存在一种执行这些操作的方法,使得最终每个顶点 ii 上的数值都等于 qiq_i,就称树 TT 为 yummy。

你也许以为小青鱼想让你找出一个方案来证明某棵树是 yummy。但这场比赛的构造题已经太多了!因此,他给你一个有 nn 个顶点、拥有许多许多边的无向图 GG。具体来说,顶点 i,ji,j 之间有 ci,jc_{i,j} 条彼此不同的边。

请计算 GG 中有多少棵 yummy 生成树。两棵生成树不同,当且仅当它们包含的边的集合不同。答案可能很大,请输出答案对 109+710^9+7 取模的结果。

输入格式

输入只包含一组数据。

第一行包含一个整数 nn(1≤n≤5001\le n\le500),表示顶点数。

第二行包含一个排列 p1,p2,…,pnp_1,p_2,\ldots,p_n,表示每个顶点最初的数值。

第三行包含一个排列 q1,q2,…,qnq_1,q_2,\ldots,q_n,表示每个顶点最终需要达到的数值。

接下来 nn 行描述矩阵 cc,每行包含 nn 个整数。第 ii 行第 jj 个整数为 ci,jc_{i,j}(0≤ci,j≤109+60\le c_{i,j}\le10^9+6),表示顶点 i,ji,j 之间的边数。

保证对所有 1≤i,j≤n1\le i,j\le n,都有 ci,i=0c_{i,i}=0 且 ci,j=cj,ic_{i,j}=c_{j,i}。p,qp,q 均为 11 到 nn 的排列。

输出格式

输出一行一个整数,表示 yummy 生成树数量对 109+710^9+7 取模的结果。

原样例 1

4
1 2 3 4
3 4 2 1
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
12

原样例 2

6
1 2 3 4 5 6
5 3 4 1 6 2
0 3 3 2 1 2
3 0 2 2 2 1
3 2 0 3 2 3
2 2 3 0 1 2
1 2 2 1 0 1
2 1 3 2 1 0
5050