At this point we already know that students love to sleep. Patrik is a
record holder in this category. He wakes up only when he needs to eat
or if he wishes to play *FIFA 20*. Therefore, his dreams usually revolve
around football. In his last dream, he found himself in the role of a football
manager of his favourite team – GNK Dinamo Zagreb.

His job is to select players that will defend the blue colors in the next season, but the board has some peculiar requests. They are:

- All players must have surnames of distinct lengths.
- Surname of a player must appear as a continuous subsequence of surnames of all players whose surnames are longer.

To make his job easier, Patrik divided the potential players in buckets such that players in -th bucket have exactly letters in their surname. In each of these buckets there are exactly players. Patrik wants to know in how many distinct ways (modulo ) can he choose the players for his squad while also conforming to the given requests.

#### Input

The first line contains two integers and .

Each of the next lines contains not necessarily distinct surnames of players. The surnames of players in -th of those lines consist of exactly lowercase letters from the English alphabet.

#### Output

In the only line you should output the answer from the task description.

#### Scoring

Subtask | Score | Constraints |
---|---|---|

and | ||

and | ||

No additional constraints. |

#### Sample Input 1

```
3 2
a b
ab bd
abc abd
```

#### Sample Output 1

`5`

#### Explanation of Sample Output 1

Patrik can choose the following teams: and .

#### Sample Input 2

```
3 3
a b c
aa ab ac
aaa aab aca
```

#### Sample Output 2

`6`

#### Sample Input 3

```
3 1
a
bc
def
```

#### Sample Output 3

`0`

## Comments