Bạn đang có ~M~ xâu, xâu thứ ~i~ được gọi là ~s_i~, độ dài mỗi xâu không quá ~6~ và chỉ có các kí tự a, b.

Yêu cầu: Bạn hãy đếm số xâu ~T~ độ dài ~N~, chỉ chứa các kí tự a, b mà không chứa bất kì một sâu ~s_i(1 \le i \le M)~ nào.

Input

• Dòng đầu tiên gồm ~2~ số nguyên dương ~N,M(1 \le N \le 10^{18}, 1 \le M \le 126)~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ là xâu ~s_i(1 \le |s_i| \le 6)~

Output

• Một dòng duy nhất, kết quả của đề bài khi chia lấy dư cho ~998244353~.

Sample Input

3 2
ab
bb

Sample Output

2

Subtask

• Có ~33\%~ số test thỏa mãn: ~1 \le N \le 20, 1 \le M \le 64~.
• Có ~67\%~ số test thỏa mãn: Như giới hạn đề bài.

Giải thích

• Các xâu thỏa mãn là: aaa, baa.