Subsequences

Datastring Research Corporation에서는 문자열 $s$의 서로 다른 부분수열의 개수가 짝수일 때 $s$를 good하다고 부른다.

문자열 $t$가 문자열 $s$의 부분수열이라는 것은, $s$에서 몇 개의 문자를 지워서 $t$를 얻을 수 있다는 뜻이다. $s$ 자신과 빈 문자열도 $s$의 부분수열로 본다. 길이가 $l$인 문자열에는 모두 $2^l$개의 부분수열이 있지만, 그중에는 서로 같은 것도 있다. 예를 들어 세 글자 문자열 $abb$의 서로 다른 부분수열은 빈 문자열, $a$, $b$, $ab$, $bb$, $abb$로 모두 6개뿐이다.

String Researcher의 책상 위에는 문자열 $s$가 놓여 있었고, 그는 이것이 good인지 알아내려 했다. 서로 다른 부분수열의 개수를 세는 일이 지루하다는 것을 깨달은 그는 곧바로 일을 시작하는 대신 도넛과 함께 커피 타임을 가지러 갔다.

돌아와 보니 누군가가 문자열 $s$를 $N-1$번 잘라 $N$개의 비어 있지 않은 부분문자열 $s_1, s_2, \dots, s_N$으로 만들어 책상 위에 흩어 놓았다. 그리고 그는 처음 문자열 $s$를 전혀 기억하지 못한다. 다만 그는 복원한 문자열 $s_{p_1}s_{p_2}\dots s_{p_N}$이 good이 되도록 하는 순열 $p = (p_1, \dots, p_N)$의 개수가 궁금하다. 순열은 모두 $N!$개 있고, 부분문자열 $s_i$가 서로 같더라도 이 순열들은 모두 다른 것으로 센다.

첫째 줄에 부분문자열의 개수 $N$이 주어진다 ($2 \leq N \leq 20$). 다음 $N$개의 줄 중 $i$번째 줄에 부분문자열 $s_i$가 주어진다.

모든 $s_i$는 비어 있지 않으며 알파벳 소문자로만 이루어져 있다. 모든 $s_i$의 길이의 합은 $10^5$을 넘지 않는다.

첫째 줄에, 순열의 순서대로 문자열 $s_i$를 이어 붙였을 때 good이 되는 순열의 개수를 출력한다.

문자열 $a + a + baa$에는 부분수열이 14개, 문자열 $a + baa + a$에는 13개, 문자열 $baa + a + a$에는 10개 있다. 부분문자열 $a$가 두 번 나타나므로, 이 각각의 문자열은 두 가지 순열로만 얻을 수 있다.