Arranging Books with Unique Initial Letters

You are given n books, each with a title. Your task is to determine the number of ways to arrange these books in a row such that no two adjacent books have titles that begin with the same letter. Note that if any two books share the same initial letter, no valid arrangement exists and the answer is 0.

If all books have distinct starting letters then every permutation is valid. Since the total number of arrangements may be large, output the answer modulo \(10^9+7\).

Input constraints:

• The first line contains an integer n (the number of books).
• The following n lines each contain a non-empty string representing the title of a book.

Example:

Input:
3
apple
banana
cherry
Output:
6

</p>

inputFormat

The input is read from stdin and consists of:

• An integer n on the first line, denoting the number of books.
• n subsequent lines where each line is a book title (a string).

outputFormat

Output a single integer on stdout representing the number of valid arrangements modulo \(10^9+7\>.

## sample

1
apple

1

</p>