33OJ
登录 注册

#P17813. [ICPC 2019 Nanchang R] Summon

[ICPC 2019 Nanchang R] Summon

题目描述

LKMCFJ 想要施放一个法术以召唤巨龙。为此,她需要将 nn 颗宝石摆放在地上,形成一个圆形的召唤环。她准备了 44 种不同的宝石:风、火、雷、电,每种宝石的数量都是无限的。

某些宝石的排列方式可能会发生爆炸,如果 LKMCFJ 不避开这些危险,她就会丧命。更确切地说,一些给定的沿顺时针方向连续 44 颗宝石的组合是不被允许的。

现在她想知道,基于这些限制,她能够制作出多少种不同的召唤环。注意,如果两个环通过旋转其中一个可以变得完全相同,则它们被视为同一种。

由于答案可能非常巨大,你只需要输出答案对 998244353998244353 取模的结果。

输入格式

第一行输入包含两个整数 nn (4≤n≤105)(4 \le n \le 10^5) 和 mm (0≤m≤256)(0\le m \le 256),分别表示召唤环所需的宝石数量,以及会导致爆炸的长度为 44 的模式数量。

接下来的 mm 行,每行包含 44 个整数,描述一个沿顺时针方向连续 44 颗宝石的、应当避免的模式。这里,我们分别用整数 0,1,2,30, 1, 2, 3 来代表四种不同类型的宝石。

输出格式

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

4 3
0 1 2 3
1 2 3 1
2 1 3 0
67

提示

翻译由 DeepSeek V4 Pro 完成