Jolly Jelly Jiffy

Chansik and his younger brother Minsik like jelly. On his way home from his friend Hongbin's house, Chansik wants to buy jelly to eat with Minsik. There are $N$ jelly shops between Chansik's house and Hongbin's house, and Chansik numbered the shops $1$ to $N$ in order of distance from his own house. Chansik can buy jelly at shop $1$ through shop $N$ in that order before he meets Hongbin, or at shop $N$ through shop $1$ in that order on the way back after he meets Hongbin. Either way he buys one jelly at each shop, and the jelly bought at shop $k$ is called jelly $k$.

Chansik has to eat the tasty jelly quickly and then study programming, so every time he buys a jelly he tidies his jelly box this way.

1. If the jelly on top is tastier than the jelly he just bought, take that jelly out.
2. Repeat step 1 until the box is empty, or until the jelly he just bought is tastier than the jelly on top.
3. Put the jelly he just bought into the box. Jelly goes in from the top.
4. Put the jellies that were taken out back in, starting with the one taken out last.

Chansik's taste decides, for every two different jellies, which of the two is tastier. Chansik recently learned a sorting algorithm, so he knows that this method usually leaves the jellies in order of taste, the tastier jelly closer to the top, whatever order he buys them in. His taste can be contradictory as a matter of logic, though. He may like lemon more than orange, strawberry more than lemon, and orange more than strawberry. In a case like that, the order the jellies are stacked in depends on the order he buys them in.

Suppose $N = 4$ and Chansik's taste is the following.

• Jelly 2 is tastier than jelly 1.
• Jelly 1 is tastier than jelly 3.
• Jelly 4 is tastier than jelly 1.
• Jelly 3 is tastier than jelly 2.
• Jelly 4 is tastier than jelly 2.
• Jelly 3 is tastier than jelly 4.

If Chansik buys the jelly before he meets Hongbin, the box fills up as in the figure below.

If Chansik buys the jelly after he meets Hongbin, the box fills up as in the figure below.

Chansik thought that other people could work out his taste from the possible box states alone, so he wrote a program that reads the two states and guesses his taste. Now he wonders whether a little less information is still enough. Write a program that guesses Chansik's taste from the box state for the case where he buys the jelly before he meets Hongbin, together with the jelly on top of the box for the case where he buys the jelly after he meets Hongbin.

The first line contains the number of jelly shops $N$. ($1 \le N \le 3000$)

The second line contains the numbers of the $N$ jellies in the box for the case where Chansik buys the jelly before he meets Hongbin, starting with the jelly on top.

The third line contains the number of the jelly on top of the box for the case where Chansik buys the jelly after he meets Hongbin.

Only inputs that have an answer are given.

On the first line, print the number of tastes possible for Chansik, modulo 1,000,000,007.

On each of the next $N$ lines, print one taste that is possible for Chansik. The $j$-th value on the $i$-th line is 1 if jelly $i$ is tastier than jelly $j$, 0 if jelly $j$ is tastier than jelly $i$, and . if $i = j$.

If several tastes are possible, print the one that comes first in lexicographic order. Two tastes are compared as strings of length $N^2$, built by joining the $N$ lines from the first line to the last with each line read from left to right, and the character 0 comes before the character 1.

With no conditions at all, the number of tastes possible for Chansik is $2^{N(N-1)/2}$.