### 问题描述 小蓝开了一家餐馆：“香煎七十二餐馆！” 据说共有七十二道菜，每道菜煎炸的次数不一，最简单的只需要煎一次，最复杂的需要煎炸整整七十二次！ 开店第一天，举办了一场餐馆派对，免费接待 $n$ 位顾客。 $n$ 位顾客坐在一个长桌上，编号 $1 \sim n$。小蓝的餐馆共有 $72$ 道菜，编号 $1 \sim 72$。每位顾客只会点一道菜，$n$ 位顾客中有 $m$ 位顾客已经点好了菜，剩下的顾客由小蓝推荐点菜。 由于每位顾客用餐的时候，都会对菜品评头论足，如果两个相邻的顾客吃的是同一道菜，他们难免会讨论，有一些吹毛求疵的顾客可能借此将消极情绪传播给他人。为了避免上述情况发生，导致影响口碑，小蓝将安排相邻的顾客的菜肴**都不相同**。 请问有多少种不同的安排方案，答案可能很大，请对 $998244353$ 取模。 **相邻**：即编号相邻，$i$ 与 $i-1$ 和 $i+1$ 相邻。注意，这是一张长桌，所以 $1$ 和 $n$ **并不相邻**。 ### 输入格式 第一行输入两个整数 $n,m$。 接下来 $m$ 行，每行两个整数 $p_i, c_i$，表示编号为 $p_i$ 的人已经点好了一份编号为 $c_i$ 的菜肴。 ### 输出格式 输出一个整数，表示合法的安排方案数。答案可能很大，请对 $998244353$ 取模。 ### 样例输入 ```bash 3 1 2 1 ``` ### 样例输出 ```bash 5041 ``` ### 说明 第一个顾客可以安排编号 $2 \sim 72$ 的菜肴，第三位顾客可以安排编号 $2 \sim 72$ 的菜肴。共计 $71^2=5041$。 ### 评测数据范围 $0 \le m\le 10^5, 3 \le n \le 10^{15}, 1 \le c_i \le 72, 1 \le p_i \le n$。 保证所有的 $p_i$ 不相同。