Building Spanning Trees

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\cdot (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(x_i,y_i)$ 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.

Input

The first line contains number $n(4\le n\le 1000)$. The second and the third lines contain arrays $x$ and $y(1\le x_i,y_i\le n)$ of length $n-3$ each.

Output

Print the number of spanning trees modulo $987654323$.

Examples