P17813 [ICPC 2019 Nanchang R] Summon

LKMCFJ wants to cast a spell to summon the dragon. To do so, she needs to place $n$ gems on the ground to form a **circular** summoning ring. She has prepared $4$ kinds of different gems: the wind, the fire, the thunder and the lightning. Each of them is unlimited. Some patterns of gems could explode and LKMCFJ would die if she does not avoid the risk. More precisely, some combinations of $4$ continuous gems in the clockwise direction in given patterns are not allowed. Now she wants to know how many different summoning rings she can make based on such limitations. Note that two necklaces are regarded as the same if they are the same after shifting one of them. Since the answer can be very large, you only need to output the answer modulo $998244353$.

The first line of the input contains two integers $n~(4 \le n \le 10^5)$ and $m~(0\le m \le 256)$ indicating the number of gems that are asked for the summoning ring, and the number of patterns of length $4$ that could explode. Each of the following $m$ lines contains $4$ integers describing a pattern of $4$ continuous gems in the clockwise order that should be avoided. Here, we use integers $0,1,2$ and $3$ to represent four different types of gems respectively.

Output an integer in a line indicating the answer modulo $998244353$.