官方题解只能做到 $O(n^3)$？玩的太差了。这题可以做到 $O(n^{\omega})$：先转化为圆周上不相交生成树的加权计数，再用快速矩阵乘法整体求出区间 DP。
从交换操作到不相交生成树
题目要求选出一棵生成树，将它的每条边恰好使用一次：交换两端的数，然后删去这条边，使初始排列 $p$ 变成 $q$。平行边需要分别计数，答案对 $10^9+7$ 取模，$n\le 500$。([QOJ][1])
令 $\operatorname{pos}_q(x)$ 表示数 $x$ 在 $q$ 中的位置，定义置换 $\pi(i)=\operatorname{pos}_q(p_i)$。它表示：初始位于顶点 $i$ 的数，最终必须移动到顶点 $\pi(i)$。
首先，$\pi$ 必须恰好是一个循环。
从没有使用任何边的状态出发，已经使用的边始终构成森林。树中的下一条边一定连接森林的两个不同连通块，否则原来的树就有环。归纳可知，每个连通块上的交换乘积恰好对应一个置换循环；交换两个不同循环中的元素，会把这两个循环合并。因此，使用全部 $n-1$ 条边之后，得到的置换一定只有一个循环。
若不满足这个条件，答案直接为 $0$。否则，沿着 $\pi$ 的循环，把顶点重新编号为 $1,2,\ldots,n$，并按这个顺序放在圆周上。下面所有编号均指重新编号后的编号，边权记为 $w_{i,j}$，即对应两个原顶点之间的平行边数量。
关键结论是：
一棵树能够实现这个循环，当且仅当把它的边画成圆内的弦后，不存在两条边在内部相交。
先证明必要性。假设两个已经处理好的连通块，其循环分别写成 $(u,a_1,\ldots,a_s)$ 和 $(v,b_1,\ldots,b_t)$。使用边 $(u,v)$ 后，两个循环合并成 $(u,a_1,\ldots,a_s,v,b_1,\ldots,b_t)$。原来两个块分别占据连续的圆弧，块内原有的边仍然不相交，新加入的边 $(u,v)$ 也不会与它们相交。归纳到整棵树即可。
充分性可以通过删除叶子证明。任意不相交树中，一定存在一个叶子，它与唯一的邻点在圆周上相邻。证明如下：选取圆周距离最短的叶子边 $(u,v)$，其中 $v$ 是叶子。如果两端不相邻，那么它较短圆弧内部的顶点只能通过 $u$ 与外部连接，因此这些内部顶点中存在一个全局叶子，其叶子边更短，矛盾。
删除这个叶子 $v$，并从目标循环中删去 $v$，剩余树依然不相交，可以归纳实现剩余循环。若目标循环中 $\pi(u)=v$，把交换 $(u,v)$ 放在操作序列最前面；若 $\pi(v)=u$，把它放在最后面，就能把 $v$ 插回正确位置。
于是，原问题等价于计算所有不相交生成树的权值之和，其中一棵树的权值为 $\prod_{(u,v)\in E(T)}w_{u,v}$。这样恰好计入每条树边选择哪一条平行边的方案数。
区间递推与矩阵乘法加速
令 $F_{l,r}$ 表示顶点区间 $[l,r]$ 上所有不相交生成树的权值之和，令 $G_{l,r}$ 表示其中包含边 $(l,r)$ 的树的权值之和。边界为 $F_{i,i}=1$。
考虑 $G_{l,r}$。删去边 $(l,r)$ 后，两个连通块必须分别占据某两个连续区间 $[l,k]$ 和 $[k+1,r]$，否则两块中的连接路径会相交。这个分割点唯一确定。
再考虑 $F_{l,r}$。令 $k$ 为顶点 $l$ 的编号最大的邻点。边 $(l,k)$ 把整棵树唯一分成两部分：$[l,k]$ 上一棵包含 $(l,k)$ 的树，以及 $[k,r]$ 上一棵任意不相交树，两者只共享顶点 $k$。因此，
$$ G_{l,r}=w_{l,r}\sum_{k=l}^{r-1}F_{l,k}F_{k+1,r}, \qquad F_{l,r}=\sum_{k=l+1}^{r}G_{l,k}F_{k,r}. $$
直接枚举区间和分割点是 $O(n^3)$。但这两个求和都可以成批转化为矩阵乘法。
令 $H_{i,j}=F_{i+1,j}$。分别把第一个递推中的 $k=i$、第二个递推中的 $k=j$ 单独提出，就得到 $G_{i,j}=w_{i,j}\bigl(H_{i,j}+\sum_{i< k< j}F_{i,k}H_{k,j}\bigr)$，以及 $F_{i,j}=G_{i,j}+\sum_{i< k< j}G_{i,k}F_{k,j}$。
现在所有需要枚举的分割点都满足严格不等式 $i< k< j$。对于依次排列的三个下标区间 $I< K< J$，贡献恰好是两次普通矩阵乘法：$G_{I,K}F_{K,J}$ 和 $F_{I,K}H_{K,J}$。边权 $w_{i,j}$ 与分割点无关，可以等到对应单元格的贡献全部收齐后再乘。
问题在于：这些矩阵本身也是待求的 DP 值，不能直接做几次整矩阵乘法。必须安排正确的分块求值顺序。 这里采用 Valiant 风格的区间递推分块加速思路。([ScienceDirect][2])
设要完成一个行下标来自 $I$、列下标来自 $J$ 的方块，其中 $I$ 整体位于 $J$ 左侧。进入这个过程时，位于 $I\cup J$ 之外的分割点贡献已经累加，块外需要的更短区间也已经计算完毕。
将 $I$ 分成左右两半 $I_0,I_1$，将 $J$ 分成左右两半 $J_0,J_1$。四块的求值顺序是：
先完成左下块 $I_1\times J_0$。 随后用分割点 $I_1$ 更新左上块 $I_0\times J_0$，用分割点 $J_0$ 更新右下块 $I_1\times J_1$，然后完成这两块。最后，分别用分割点 $I_1$ 和 $J_0$ 更新右上块 $I_0\times J_1$，再完成右上块。
每次“更新”都是前面所说的两次矩阵乘法。这个顺序保证每次使用的源块都已经完成，并且每个三元组 $i< k< j$ 恰好被计入一次。对于额外依赖 $H_{i,j}=F_{i+1,j}$，由于同一列总是先完成下方的状态，它也总能及时获得。
整个上三角矩阵则先递归求出左半、右半的两个上三角部分，再用上述过程求出连接左右两半的矩形。
实现中不必单独保存 $H$，因为它只是 $F$ 向上错一行。具体维护 $F,G,D$ 三张表，其中尚未结算的 $F_{i,j}$ 暂存 $\sum_{i< k< j}G_{i,k}F_{k,j}$，$D_{i,j}$ 暂存 $\sum_{i< k< j}F_{i,k}F_{k+1,j}$。结算时先令 $G_{i,j}=w_{i,j}(D_{i,j}+F_{i+1,j})$，再执行 $F_{i,j}\mathrel{+}=G_{i,j}$。
设 $s$ 阶矩阵乘法耗时为 $M(s)=O(s^\omega)$，其中固定的 $\omega>2$。完成一个 $s\times s$ 方块的时间满足 $C(s)=4C(s/2)+8M(s/2)+O(s^2)$，所以 $C(s)=O(s^\omega)$。整个上三角矩阵的时间满足 $T(n)=2T(n/2)+C(n/2)$，因此同样是 $O(n^\omega)$。