/* name: perm
 * author: 5ab
 * created at: 2023-09-02
 */
#include <iostream>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (x > y) x = y; };

using ll = long long;
const int max_n = 1e6, mod = 998244353;

int a[max_n], b[max_n];

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int cas, n, m;
	
cas = 1;
	while (cas--)
	{
		cin >> n >> m;
		for (int i = 0; i < m; i++)
			cin >> a[i], a[i]--;
		fill(b, b + n, 1);
		
		bool isp = 0;
		for (int i = 1; i < m; i++)
		{
			if (a[i] < a[i - 1])
				isp = true;
			if (isp)
				b[a[i]] = 0;
		}
		for (int i = 1; i < n; i++)
			b[i] += b[i - 1];
		for (int i = 0; i < n; i++)
			b[i]--;
		
		int ans = 1, cfc = 0;
		if (b[a[0]] != 0)
		{
			cout << "0\n";
			continue;
		}
		for (int i = 0, j = 1; i < m; i++, j++)
		{
			if (i > 0 && a[i] < a[i - 1])
				break;
			if (i == m - 1 || a[i + 1] < a[i])
				cfc += 2;
			else
				cfc++;
			while (j < (i == m - 1 ? n : b[a[i + 1]]))
				ans = 1ll * ans * cfc % mod, cfc++, j++;
			// cerr << cfc << " " << j << endl;
		}
		
		cout << ans << "\n";
	}
	
	return 0;
}
// started coding at: 09-02 10:20:56