Valid Permutations Avoiding Adjacent Similar Starting Letters

You are given a list of n strings. Your task is to determine in how many ways you can rearrange these strings such that no two adjacent strings start with the same letter. If there exists any pair of strings that start with the same letter, then no valid permutation is possible, and the answer should be 0.

In mathematical terms, if we let \(S = [s_1, s_2, \dots, s_n]\) be the list of strings, then find the number of permutations \(\sigma\) of \(\{1,2,\dots,n\}\) such that for every index \(i = 2,3,\dots,n\), the condition \[ s_{\sigma(i)}[0] \neq s_{\sigma(i-1)}[0] \] holds. If there exists any duplicate among the first characters \(\{s_1[0], s_2[0], \dots, s_n[0]\},\) output 0.

If all the strings start with distinct letters, the answer is simply \(n!\) (i.e. the factorial of \(n\)).

inputFormat

The input is given from standard input (stdin) and has the following format:

The first line contains an integer n (1 ≤ n ≤ 10), the number of strings.
Each of the following n lines contains a non-empty string consisting of lowercase letters.

It is guaranteed that the strings have at least one character.

outputFormat

Output to standard output (stdout) a single integer representing the number of valid permutations where no two adjacent strings share the same starting letter.

4
apple
banana
cherry
date

24