题目描述

给定 n，请求出满足下列条件的 1∼n 的排列a_1,a_2,…,a_n 的数量： 给定序列 x_1,x_2,…,x_m，满足此序列为排列 a 的字典序最小的长度为 m 的子序列。 请输出答案对 998244353 取模的结果。

输入格式

第一行，两个正整数 n,m。 第二行，m 个正整数 x_1,x_2,…,x_m。

输出格式

仅一行，一个正整数，表示答案对 998244353 取模的结果

输入输出样例 #1

输入 #1

3 2
1 2

输出 #1

3

输入输出样例 #2

输入 #2

3 2
2 1

输出 #2

2

【样例解释1】 如下 3 个排列满足要求：[1,2,3]，[1,3,2]，[3,1,2]。

【样例解释2】 如下 2 个排列满足要求：[2,3,1]，[3,2,1]。

【数据范围】 对于 10% 的数据，n≤8。

对于 30% 的数据，n≤500。

对于另外 20% 的数据，所有的 1≤i<m 均满足 x_i<x_(i+1)。

对于另外 20% 的数据，m≥2 且 x_2=1。

对于 100% 的数据，1≤m≤n≤2.5×〖10〗^5，1≤x_i≤n 且 x_i 互不相同。