Consider an undirected, complete, simple graph G on n vertices. The vertices of G are labeled from 1 to n. Specifically, each pair of distinct vertices is connected by a single undirected edge, so there are precisely n⋅(n−1)/2 edges in this graph.
You are given a set E that consists of n−3 edges of this graph G. More precisely, you are given two arrays x and y with n−3 elements each. For each valid i (xi,yi) is one of the edges in E.
A spanning tree of G is a subset of exactly n−1 edges of G such that the edges connect all n vertices. You may note that the edges of a spanning tree do indeed form a tree that is a subgraph of G and spans all its vertices.
We are interested in spanning trees that contain all of the edges in the provided set E. Find the number of such spanning trees modulo 987654323. Two spanning trees are different if there is an edge of G that is in one of them but not in the other.
The first line contains number n (4≤n≤1000). The second and the third lines contain arrays x and y (1≤xi,yi≤n) of length n−3 each.
Print the number of spanning trees modulo 987654323.