Problem Description

We define a test sentence as a string that contains all lowercase English letters.

Now you are given $N$ words. Find the maximum number of test sentences that can be formed from these words.

Each word can be used at most once in a test sentence, and the order of words in the sentence does not matter, i.e., uvijek jedem sarmu and jedem sarmu uvijek are considered the same.

Input Format

The first line contains an integer $N$, the number of words.

The next $N$ lines each contain one word, with length not exceeding $100$.

It is guaranteed that all words are distinct.

Output Format

Output the maximum number of test sentences that can be formed.

9
the
quick
brown
fox
jumps
over
a
sleazy
dog

2

3
a
b
c 

0

15
abcdefghijkl
bcdefghijklm
cdefghijklmn
defghijklmno
efghijklmnop
fghijklmnopq
ghijklmnopqr
hijklmnopqrs
ijklmnopqrst
jklmnopqrstu
klmnopqrstuv
lmnopqrstuvw
mnopqrstuvwx
nopqrstuvwxy
opqrstuvwxyz 

8189

Hint

Constraints

$1\le N\le 25$.

Sample Explanation

Explanation for Sample 1

All words except a must be used in the test sentence, because each of them contains a letter that cannot be found in any other word. Therefore, there are two possible ways. The first is the sentence containing all words, and the second is the sentence formed by all words except a.

Explanation for Sample 3

This sample consists of consecutive lowercase English letters.

Notes

This problem is translated from COCI2013-2014 CONTEST #6 T2 FONT.

Translated by ChatGPT 5