숌 크로스워드

숌 크로스워드는 검은 칸이 섞인 흔한 크로스워드를 살짝 변형한 퍼즐이다. 영어 단어 4개가 주어질 때, 아래 규칙을 모두 만족하는 배치를 몇 가지나 만들 수 있는지 세는 것이 목표다.

규칙은 다음과 같다.

1. 네 단어는 각각 정확히 한 번씩 사용한다.
2. 네 단어 중 두 개는 가로로(왼쪽에서 오른쪽으로) 쓴다.
3. 나머지 두 개는 세로로(위에서 아래로) 쓴다.
4. 각 가로 단어는 두 세로 단어 모두와 정확히 한 칸에서 교차해야 한다.
5. 각 세로 단어는 두 가로 단어 모두와 정확히 한 칸에서 교차해야 한다.
6. 두 가로 단어는 서로 다른 행에 놓이며, 두 단어 사이에는 가로 단어가 하나도 없는 행이 적어도 한 줄 있어야 한다.
7. 두 세로 단어는 서로 다른 열에 놓이며, 두 단어 사이에는 세로 단어가 하나도 없는 열이 적어도 한 칸 있어야 한다.

두 배치가 같은지는 다음과 같이 판단한다. 가장 왼쪽 칸의 열을 0, 가장 위쪽 칸의 행을 0으로 두었을 때, 네 단어의 상대적 위치가 모두 같으면 같은 배치로 본다. (회전이나 대칭은 서로 다른 배치로 센다.)

예를 들어 단어가 zaxb, axc, cxd, bxdy이면 아래 두 가지 배치를 만들 수 있다.

zaxb x x cxd   y

zaxcx xbxdy

네 개의 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이는 3 이상 15 이하이며, 네 단어는 서로 다르다.

만들 수 있는 서로 다른 배치의 수를 한 줄에 출력한다.