Gấu và phép nén xâu

Cho bảng chữ cái chỉ gồm sáu chữ cái đầu tiên: a, b, c, d, e, f.

Bạn được cho $q$ phép biến đổi. Phép thứ $i$ gồm một xâu $a_i$ độ dài $2$ và một xâu $b_i$ độ dài $1$. Không có hai phép nào có cùng $a_i$.

Với một xâu $s$, bạn có thể áp dụng phép thứ $i$ nếu hai ký tự đầu tiên của $s$ đúng bằng $a_i$. Khi áp dụng, hai ký tự đầu của $s$ bị xóa và thay bằng ký tự $b_i$. Như vậy mỗi lần áp dụng phép biến đổi làm độ dài của $s$ giảm đúng $1$.

Các phép có thể được áp dụng theo thứ tự bất kỳ và mỗi phép có thể dùng nhiều lần. Với một số xâu, đến một lúc nào đó không thể rút gọn thêm được vì hai ký tự đầu không khớp với bất kỳ $a_i$ nào.

Ta muốn bắt đầu từ một xâu độ dài $n$ (chỉ gồm sáu chữ cái trên) và thực hiện đúng $n-1$ phép để cuối cùng thu được xâu một ký tự "a". Hỏi có bao nhiêu xâu ban đầu độ dài $n$ mà từ đó có thể rút gọn về "a"?

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• $q$ dòng tiếp theo, mỗi dòng chứa xâu $a_i$ (độ dài $2$) và xâu $b_i$ (độ dài $1$), cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên: số lượng xâu độ dài $n$ mà có thể rút gọn về "a".

Ràng buộc

• $2\le n\le 6$
• $1\le q\le 36$
• $|a_i|=2$, $|b_i|=1$; tất cả $a_i$ đôi một khác nhau.
• Mọi ký tự trong $a_i$ và $b_i$ đều thuộc {a, b, c, d, e, f}.

Ví dụ