P17813 [ICPC 2019 Nanchang R] Summon

LKMCFJ 想要施放一个法术以召唤巨龙。为此，她需要将 $n$ 颗宝石摆放在地上，形成一个**圆形**的召唤环。她准备了 $4$ 种不同的宝石：风、火、雷、电，每种宝石的数量都是无限的。 某些宝石的排列方式可能会发生爆炸，如果 LKMCFJ 不避开这些危险，她就会丧命。更确切地说，一些给定的沿顺时针方向连续 $4$ 颗宝石的组合是不被允许的。 现在她想知道，基于这些限制，她能够制作出多少种不同的召唤环。注意，如果两个环通过旋转其中一个可以变得完全相同，则它们被视为同一种。 由于答案可能非常巨大，你只需要输出答案对 $998244353$ 取模的结果。

第一行输入包含两个整数 $n$ $(4 \le n \le 10^5)$ 和 $m$ $(0\le m \le 256)$，分别表示召唤环所需的宝石数量，以及会导致爆炸的长度为 $4$ 的模式数量。 接下来的 $m$ 行，每行包含 $4$ 个整数，描述一个沿顺时针方向连续 $4$ 颗宝石的、应当避免的模式。这里，我们分别用整数 $0, 1, 2, 3$ 来代表四种不同类型的宝石。

在一行中输出一个整数，表示答案对 $998244353$ 取模的结果。

翻译由 DeepSeek V4 Pro 完成