Critical Misread#3448

Critical Misread

1 second
128 megabytes

You are given strings s_1, s_2, \ldots, s_k consisting of lowercase Latin letters.

Find the number of strings of length consisting of lowercase Latin letters that contain none of the strings s_1, s_2, \ldots, s_k as a substring (a contiguous sequence of characters). Since this number can be large, output it modulo .

Input

The first line contains two integers and k~(1 \le n \le 10^9, 1 \le k \le 10) — the length of the strings to be counted and the number of forbidden strings.

Each of the next lines contains one string s_i. Each string consists of lowercase Latin letters and has length from to inclusive.

Output

Print a single integer — the number of strings of length that contain none of the strings s_i as a substring, taken modulo .

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading