Problem Statement

You are given a set $S=\lbrace s _ 1,s _ 2,\ldots,s _ M\rbrace$ of non-empty strings of length at most $6$ consisting of a and b. Find the number of strings $T$ of length $N$ consisting of a and b that satisfy the following condition:

• $T$ does not contain $s _ i$ as a consecutive substring for any $s _ i\in S$.

Since the answer can be enormous, find it modulo $998244353$.

Constraints

• $1\leq N\leq10^{18}$
• $1\leq M\leq126$
• $N$ and $M$ are integers.
• $s _ i$ is a non-empty string of length at most $6$ consisting of a and b.
• $s _ i\neq s _ j\ (1\leq i\lt j\leq M)$

Input

The input is given from Standard Input in the following format:

N M
s _ 1
s _ 2
\vdots
s _ M

Output

Print the answer modulo $998244353$ in a single line.