Herkabe Teacher and the Aesthetic Leaderboard

Teacher Herkabe wants his leaderboard to be aesthetically pleasing. For this, he mandates that if any two names in the leaderboard share a common prefix, then every name positioned between them must also share that same prefix. In other words, for any prefix (P) and any two names that both start with (P), all names that appear between them in the leaderboard must also start with (P).

Given (n) student names, count the number of different leaderboards (permutations of the names) that satisfy this condition. Since the answer can be very large, output the answer modulo (10^9+7).

A valid leaderboard must ensure that, for every prefix (P) that is common to at least two names, the names having prefix (P) appear consecutively in the permutation.

inputFormat

The first line contains an integer (n) (the number of students). The following (n) lines each contain a non-empty string representing a student's name. All names consist of lowercase English letters.

outputFormat

Output a single integer: the number of valid leaderboards modulo (10^9+7).

sample

2
ab
ac

2