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 .
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.
Print a single integer — the number of strings of length that contain none of the strings s_i as a substring, taken modulo .
Example 1
Example 2
Example 3