Reordering Train Cars (Small)

Yahya is a curious kid, so playing with his toys makes him ask questions. Today's question started when his father brought him a set of toy train cars. Each car has one lowercase letter written on one side.

At first he connected cars with no goal in mind and got bored, so he made up a problem of his own.

He now has $N$ groups of already connected cars. Each group is written as one string of lowercase letters. He wants to count the ways to join all $N$ groups into a single line so that the result is a valid train. A train is valid when all cars carrying the same letter sit next to each other.

The figure shows one way to join "ab", "bc" and "cd" into the valid train "ab bc cd". Joining them as "cd ab bc" is not valid, because the two "c" cars end up apart.

Groups are distinguishable. If two groups carry the same string, placing them in either order counts as two different ways.

The letters are written on one side of the cars only, so a group cannot be reversed. A group reading "ab" can never be read as "ba".

The first line has the number of test cases $T$. The first line of each test case has one integer $N$, the number of groups of connected cars. The next line has $N$ strings separated by a single space. Each string describes one group and uses lowercase English letters only.

Limits

• $1 \le T \le 100$
• $1 \le N \le 10$
• Each string has length between $1$ and $100$.

For each test case, print one line in the form "Case #x: y", where $x$ is the test case number starting from 1 and $y$ is the number of different ways to build a valid train. This number can be very large, so print it modulo 1,000,000,007.

In the first example, the only valid train comes from joining "ab", "bbbc" and "cd" in that order.

The second example has 4 ways. Two groups read "aa", so there are 2 orders that turn them into "aaaa", and there is 1 way to join "bc" with "c" into "bcc". Then "aaaa" and "bcc" can be placed in 2 orders, which gives $2 \times 2 = 4$.

The third example has no valid train. Both "abc"+"bcd" and "bcd"+"abc" leave the two "b" cars and the two "c" cars apart.