엉킨 실 매듭

탁자 위에 여러 색의 실이 놓여 있다. 모든 실은 서로 다른 색이며, 각 실의 양 끝은 하나의 직선 위 어딘가에 놓여 있다. 따라서 각 색은 정확히 두 번 나타난다.

모든 실을 하나의 큰 고리로 묶어야 한다. 한 번의 작업에서는 현재 서로 이웃한 두 자유 끝을 골라 서로 묶는다. 두 끝이 이미 같은 연결 조각에 속한다면 그 작업은 별도의 고리를 닫아 버리므로, 전체 작업의 마지막에 하나의 큰 고리를 완성하는 경우가 아니라면 허용되지 않는다.

작업을 끝낼 수 있는 서로 다른 묶는 순서의 수를 구하라.

입력은 여러 개의 색 패턴으로 이루어진다. 각 패턴은 길이가 22 이하인 소문자 단어이다. 입력은 # 하나만 있는 줄로 끝난다.

각 입력 패턴마다, 그 패턴을 완성할 수 있는 올바른 묶는 순서의 수를 한 줄에 출력한다. 어떤 문자가 정확히 두 번 나타나지 않아 패턴이 올바르지 않다면 그 줄의 출력은 0이다.