Problem C
Vaccine Manufacturing
An Italian lab claims that they are really close to finding a vaccine for the upcoming COVID-23. To manufacture it, they have $N$ vaccine components encoded as strings: none of those alone can cure the virus, but there is a combination of three of them (repetition is allowed) which the researchers believe will be 100% effective to cure the virus.
The researchers know that this “ultimate vaccine” made by concatenating its components’ string encodings must be a palindrome! A palindrome is a sequence of characters that reads the same backward as forward, such as madam or racecar.
As you may know, there is already a very close competition over finding a promising vaccine for COVID-23, so the lab manager wants to know how many combinations of these $N$ components have to be tested to find the working vaccine. Since this number might be huge, you are asked to only print its remainder after division by $1\, 000\, 000\, 007$.
Input
The first line contains one integer: $N$, the number of vaccine components.
Each of the next $N$ lines contains the string representation $M_ i$ of the $i$-th vaccine component.
Output
You need to write a single line containing the remainder of the number of combinations of three vaccine components who form a palindrome after being divided by $1\, 000\, 000\, 007$.
Constraints
-
$1 \le N \le 10\, 000$.
-
$M_ i$ is always between $1$ and $100$ characters long.
-
Different vaccine components may sometimes be represented by the same string encoding.
Example
In the second example below there are $3$ ways to choose three vaccine components:
-
madam, im, adam
-
madam, adam, adam
-
madam, madam, madam
| Sample Input 1 | Sample Output 1 |
|---|---|
3 a b a |
15 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 madam im adam |
3 |
