젤리 취향 맞히기

찬식이와 동생 민식이는 젤리를 좋아한다. 찬식이는 친구 홍빈이네 집에 갔다가 돌아오는 길에 민식이와 같이 먹을 젤리를 사려고 한다. 찬식이네 집과 홍빈이네 집 사이에는 젤리 가게가 $N$개 있고, 찬식이는 자기 집에서 가까운 순서대로 가게에 $1$번부터 $N$번까지 번호를 매겼다. 찬식이는 홍빈이를 만나기 전에 $1$번 가게부터 $N$번 가게까지 순서대로 젤리를 사거나, 홍빈이를 만난 뒤 돌아오는 길에 $N$번 가게부터 $1$번 가게까지 순서대로 젤리를 살 수 있다. 어느 쪽이든 가게마다 젤리를 하나씩 사고, $k$번 가게에서 산 젤리를 $k$번 젤리라고 부른다.

찬식이는 집에 돌아와서 맛있는 젤리만 후딱 먹고 프로그래밍 공부를 해야 하기 때문에, 젤리를 하나 살 때마다 아래 방법으로 젤리 보관함을 정리한다.

1. 가장 위에 있는 젤리가 새로 산 젤리보다 맛있으면 그 젤리를 꺼낸다.
2. 보관함이 빌 때까지, 또는 새로 산 젤리가 가장 위에 있는 젤리보다 맛있어질 때까지 1번 작업을 반복한다.
3. 새로 산 젤리를 보관함에 넣는다. 젤리는 위로 넣어진다.
4. 꺼내 둔 젤리를 나중에 꺼낸 것부터 차례로 다시 넣는다.

찬식이의 취향은 서로 다른 두 젤리마다 어느 쪽이 더 맛있는지를 정해 준다. 찬식이는 최근에 정렬 알고리즘을 배웠기 때문에, 보통은 이 방법으로 젤리를 어떤 순서로 사더라도 맛있는 젤리가 위로 오게 정리된다는 것을 알고 있다. 하지만 찬식이의 취향은 논리적으로 따지면 모순일 때가 있다. 예를 들어 오렌지맛보다 레몬맛을, 레몬맛보다 딸기맛을, 딸기맛보다 오렌지맛을 더 좋아할 수 있다. 이런 경우에는 젤리를 사는 순서에 따라 보관함에 쌓이는 순서가 달라진다.

$N = 4$이고 찬식이의 취향이 다음과 같다고 하자.

• 젤리 2가 젤리 1보다 맛있다.
• 젤리 1이 젤리 3보다 맛있다.
• 젤리 4가 젤리 1보다 맛있다.
• 젤리 3이 젤리 2보다 맛있다.
• 젤리 4가 젤리 2보다 맛있다.
• 젤리 3이 젤리 4보다 맛있다.

찬식이가 홍빈이를 만나기 전에 젤리를 사면 보관함이 아래 그림과 같이 채워진다.

반면 찬식이가 홍빈이를 만난 뒤에 젤리를 사면 보관함이 아래 그림과 같이 채워진다.

찬식이는 보관함으로 가능한 상태만 알아도 남들이 자기 취향을 알아낼 수 있겠다는 생각이 들어, 두 상태를 입력받아 자기 취향을 추측하는 프로그램을 짰다. 이제 찬식이는 정보를 조금 덜 알고도 취향을 알아낼 수 있을지 궁금해졌다. 홍빈이를 만나기 전에 젤리를 샀을 때의 보관함 상태와, 홍빈이를 만난 뒤에 젤리를 샀을 때 가장 위에 있는 젤리가 주어질 때 찬식이의 취향을 추측하는 프로그램을 작성하여라.

첫째 줄에 젤리 가게의 수 $N$이 주어진다. ($1 \le N \le 3000$)

둘째 줄에 찬식이가 홍빈이를 만나기 전에 젤리를 샀을 때 보관함에 있는 젤리 $N$개의 번호가 가장 위에 있는 젤리부터 차례로 주어진다.

셋째 줄에 찬식이가 홍빈이를 만난 뒤에 젤리를 샀을 때 보관함의 가장 위에 있는 젤리의 번호가 주어진다.

답이 존재하는 입력만 주어진다.

첫째 줄에 찬식이의 취향으로 가능한 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

둘째 줄부터 $N$개의 줄에 찬식이의 취향으로 가능한 것 하나를 출력한다. $i$번째 줄의 $j$번째 값은 $i$번 젤리가 $j$번 젤리보다 맛있으면 1, $j$번 젤리가 $i$번 젤리보다 맛있으면 0, $i = j$이면 .이다.

가능한 취향이 여러 가지라면 사전순으로 가장 앞서는 것 하나를 출력한다. 두 취향은 $N$개의 줄을 첫째 줄부터 차례로, 각 줄은 왼쪽부터 오른쪽으로 이어 붙인 길이 $N^2$짜리 문자열로 비교하고, 문자 0이 문자 1보다 앞선다.

참고로 아무 조건이 없다면 찬식이의 취향으로 가능한 경우의 수는 $2^{N(N-1)/2}$이다.