“Can you answer this million dollar question ?” said the presenter to Little Achraf.
“Yes”, he responded.
“Ok … here is the question”.

We define a sequence A of strings of order L as follows:

$A[n] = \sum\limits_{i = 0}^{L-1} A[n-L+i]; n \ge L+1$; where addition refers to string concatenation
$A[n] \in [a-z A-Z 0-9]; 1 \le n \le L$.

Now, given some constraints of the form “The $nth$ character of $A[x]$ is equal to c”; you need to calculate the number of possible sequences (possibly none) that satisfy all the given constraints.

Input Format:

First line contains L and C, the order of the sequence A and the number of constraints, respectively.
Each of the next C lines contain n, x, and a character c meaning “The $nth$ character of $A[x]$ is equal to c”.

Output Format:

Print a single number denoting the number of possible sequences that satisfy all the given constrains modulo $10^9 + 7$.

Constraints:

• $2 \le L \le 100$
• $0 \le C \le 10^4$
• $1 \le n \le 10^{15}$
• $x \le 10^{15}$
• character $c \in [a-zA-Z0-9]$