Reordering Train Cars (Large)

Yahya asks himself interesting questions whenever he plays with his toys. Today's question started when his father brought him a box of toy train cars. Each car has one lowercase English letter written on one of its sides.

At first he connected cars with no particular goal in mind, but he soon got bored and decided to define a new problem.

Right now Yahya has $N$ bundles of already connected cars. Each bundle can be written as a string of lowercase letters. He wants to count the ways to connect all $N$ bundles into one 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 picture above shows one way to connect "ab", "bc" and "cd" into the valid train "ab bc cd". The order "cd ab bc" is not valid, because the two cars carrying 'c' would be separated.

Two bundles written with the same string are still different bundles. Swapping their positions counts as a different way.

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

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains the number of bundles of connected cars $N$. The next line contains $N$ strings separated by a single space. Each string describes one bundle and consists of lowercase English letters only.

Limits

• $1 \le T \le 100$
• $1 \le N \le 100$
• The length of each string is 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 value can be very large, so print it modulo 1,000,000,007.

In the first test case of the sample input, the only way is to join "ab", "bbbc" and "cd" in that order.

The answer for the second test case is 4. There are two bundles written "aa", so there are two orders that join them into "aaaa". The bundles "bc" and "c" have only one order that makes "bcc". After that, "aaaa" and "bcc" can be placed in two orders, so the total is $2 \times 2 = 4$.

In the third test case, both "abc"+"bcd" and "bcd"+"abc" separate the two 'b' cars and the two 'c' cars, so no valid train exists.