Font

Time limit1sMemory limit256 MB

Summary

Count the subsets of the given words whose letters together cover all 26 lowercase letters.

Level: Medium4 of 10
Topics: Brute force, Bit manipulation
Solved: No attempts yet

Problem

Sanggeun wants to write one sentence that tests the font he made. The font contains only lowercase letters, so the sentence has to be written in lowercase letters as well.

The test sentence has to contain all 26 lowercase letters.

Anyone who has solved a lot of problems should already sense what this problem asks after reading only this far.

Sanggeun has one dictionary with $N$ words in it. The test sentence can only use words from the dictionary, and each word can be used only once. The order of the words does not matter. ("uvijek jedem sarmu" and "jedem sarmu uvijek" are the same sentence.)

Write a program that counts the test sentences Sanggeun can make.

Input

The first line contains the number of words $N$ ( $1 \le N \le 25$ ). Each of the next $N$ lines contains one word from the dictionary. A word consists of lowercase letters only and is at most 100 characters long. No word is given twice.

Output

Print the number of test sentences Sanggeun can make.

Examples3

Example 1

Input

9
the
quick
brown
fox
jumps
over
a
sleazy
dog

Expected output

Example 2
Input
```
3
a
b
c
```
Expected output
```
0
```

Example 3

Input

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

Expected output