考虑一棵具有 $n$ 个顶点的树 $T = (V, E)$，顶点编号为 $1$ 到 $n$。第 $i$ 个顶点初始时有一个值 $p_i$。所有 $p_i$ 的值均为 $1$ 到 $n$ 之间的不同整数。换句话说，$p$ 是一个长度为 $n$ 的排列。
你需要执行 $n-1$ 次以下操作：
- 选择一条边 $e = (x, y) \in E$。
- 交换 $p_x$ 和 $p_y$ 的值。
- 从 $E$ 中移除边 $e$。
最终，$T$ 将变成一个没有边的图。如果存在一种应用这些操作的方式，使得对于所有 $1 \le i \le n$，最终的 $p_i$ 变为 $q_i$，则称这棵树 $T$ 是“美味的”（yummy）。
你可能认为 Little Cyan Fish 想找一个方案来证明 $T$ 是美味的。但这场比赛中的构造题太多了！因此，他给了你一个具有 $n$ 个顶点和许多边的无向图 $G$。实际上，顶点 $i$ 和 $j$ 之间有 $c_{i,j}$ 条不同的边。
Little Cyan Fish 希望你计算这个图中包含多少个美味的生成树。如果两棵生成树包含的边集不同，则认为它们是不同的。由于答案可能非常大，请输出答案对 $10^9 + 7$ 取模的结果。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 500$)，表示图的节点数。
下一行包含一个排列 $p_1, p_2, \dots, p_n$，表示每个节点初始时的值。
下一行包含一个排列 $q_1, q_2, \dots, q_n$，表示每个节点最终的值。
接下来的 $n$ 行描述矩阵 $c$，每行包含 $n$ 个整数。第 $i$ 行的第 $j$ 个整数描述了 $c_{i,j}$ 的值 ($0 \le c_{i,j} \le 10^9 + 6$)，表示节点 $i$ 和 $j$ 之间的边数。
保证 $c_{i,i} = 0$，且对于所有 $1 \le i, j \le n$，都有 $c_{i,j} = c_{j,i}$。
输出格式
输出一行，包含一个整数，表示该图中美味生成树的数量对 $10^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
输出 1
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
输出 2
5050