Justin wants to create a new password for his Roblox account. He has the following requirements for such a password:

• It must consist of $N$ lowercase letters.
• He specifies $M$ two-letter strings that cannot appear as a substring in the password, e.g., ab or cc.

Help Justin count the number of possible passwords he could create, modulo $10^9 + 7$.

Input

The first line of input consists of two integers $N$ and $M$.
The next $M$ lines each contain a two-letter string which cannot appear in the password.

Output

Output the required number of possible passwords, modulo $10^9 + 7$.

Constraints

For all subtasks, $1 \le N \le 10^4$; $0 \le M \le 676$.
Subtask 1 (25%): $N \le 5$
Subtask 2 (25%): $M = 0$
Subtask 3 (50%): No additional constraints