Кроссворды

면접 대비

시간 제한2초메모리 제한1024 MB

요약

서로 다른 네 단어가 주어질 때, 가로 두 개와 세로 두 개가 서로 교차하도록 배치하는 십자말풀이의 가짓수를 센다.

난이도: 보통10점 중 4점
유형: 구현, 완전 탐색, 문자열
정답자: 아직 제출이 없습니다

문제

Саламандер очень любит своих существ и поэтому решил скрасить им времяпровождение в чемодане. Он решил каждому существу дать по кроссворду, однако их много, и кроссвордов соответственно нужно тоже достаточное число. Саламандер решил, что для простоты каждый кроссворд будет состоять ровно из 4 слов --- 2 по вертикали и 2 по горизонтали, а также у них будет ровно 4 попарных пересечения, образующих прямоугольник, возможно нулевой площади.

Саламандер уже придумал 4 различных слова для нового кроссворда, теперь он хочет знать количество различных кроссвордов, которые из них можно составить. Он считает, что два кроссворда различны, если их нельзя наложить друг на друга так, чтобы они полностью совпали. Помогите ему посчитать нужное ему количество способов.

입력

В $i$ -й из 4 строк содержится $w\_i$ --- $i$ -е слово, придуманное Саламандром ( $2 \le |w\_i| \le 30$ ). Гарантируется, что каждое слово состоит только из строчных букв латинского алфавита и что все слова попарно различны.

출력

В единственной строке выведите количество способов составить кроссворд из данных слов. Учтите, что слова по горизонтали записываются слева направо, а слова по вертикали --- сверху вниз.

힌트

Оба возможных кроссворда представлены на картинках:

예제1

예제 1
입력
```
internet
ifmo
rampage
olympiad
```
예상 출력
```
2
```