#define _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <ctime>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int) n; i++)
#define seta(a, b) memset(a, b, sizeof(a))

const string name = "army";

const int NMAX = 16;
const int STMAX = 15000000;

int n, m, p[NMAX], now[NMAX], d[NMAX], st[NMAX], need[NMAX];
int ans[STMAX], answer;

int main()
{
	freopen((name + ".in").data(), "r", stdin);
	freopen((name + ".out").data(), "w", stdout);

	cin >> n >> m;
	forn(i, n)
		need[i] = n;
	forn(i, m)
	{
		cin >> p[i];
		p[i]--;
		if (i) need[p[i]] = p[i - 1];
	}

	st[0] = 1;
	forn(i, n)
		st[i + 1] = st[i] * 3;

	int tmp, num, yl, all;
	seta(ans, 0);
	ans[0] = 1;
	answer = 0;
	d[0] = -1;
	now[n] = 1;

	forn(i, st[n])
		if (ans[i] > 0)
		{
			tmp = i, num = 1, yl = 1, all = 0;
			forn(j, n)
			{
				now[j] = tmp % 3, tmp = tmp / 3;
				if (now[j] == 1)
					d[num++] = j;
				if (now[j]) all++;
			}
			d[num] = n;

			if (all == n && num == m + 1)
				answer += ans[i];

			forn(j, n)
				if (now[j] == 0 && now[need[j]])   
				{
					while (yl <= m && d[yl] < j)
						yl++;
					if (d[yl] == n)                         
						ans[i + st[j]] += ans[i];
					else
						ans[i + st[j] + st[d[yl]]] += ans[i];
				}
		}
	cout << answer << endl;
	cerr << clock() << endl;

	return 0;
}
