#P18382. Alternative Accounts 2

Alternative Accounts 2

Alternative Accounts 2

题目描述

在一场钓鱼比赛中,共有 nn 名选手报名,每名选手恰好注册了两个不同账号,合计 2n2n 个账号。所有选手都遵守同一条规则:每次参赛时,必须使用自己两个账号中当前排名较差的那个。排名数字越小越好,因此,若两个账号的当前排名分别为 x,yx,y,该选手只能使用排名为 max⁡(x,y)\max(x,y) 的账号参赛。

按初始排名将账号编号为 1,2,…,2n1,2,\ldots,2n。设 pip_i 表示当前排名第 ii 的账号,最初有 pi=ip_i=i。

之后进行了 mm 场比赛,每场恰有一名选手参赛。第 ii 场比赛中,当前排名为 kik_i 的账号参赛,并上升一名,即交换 pkip_{k_i} 与 pki−1p_{k_i-1}。保证 ki≥2k_i\ge2。

给定全部比赛记录,求有多少种方法将这 2n2n 个账号划分成 nn 个无序的二元组,使每个二元组代表同一名选手的两个账号,并且在每场比赛发生时,参赛账号都确实是该组中当前排名较差的账号。

两个划分不同,当且仅当至少有一个账号在两个划分中的同组选手账号不同。选手没有额外编号,二元组内部和二元组之间的排列顺序都不产生新的方案。

答案对 998244353998244353 取模。

输入格式

第一行包含两个整数 n,mn,m(1≤n,m≤50001\le n,m\le5000),分别表示选手人数与比赛场数。

接下来 mm 行,每行包含一个整数 kik_i(2≤ki≤2n2\le k_i\le2n),表示第 ii 场参赛账号在该场比赛开始前的当前排名。

本题输入只有一组数据。

输出格式

输出一个整数,表示符合全部记录的账号配对方案数模 998244353998244353 的结果。

样例输入 1

1 1
2

样例输出 1

1

样例输入 2

2 2
2
3

样例输出 2

0