题目描述

题目译自 XXVI Olimpiada Informatyczna – I etap Klubowicze 2。

我们再次来到了字节克讨论俱乐部。这个俱乐部有 $2^{n}$ 名成员，每人都对 $n$ 个基本问题表达了自己的看法。这些问题的具体内容不重要，只需知道每个问题都有两种答案可选。每个人的看法可以用一串二进制位表示，转化为十进制后是 $0$ 到 $2^{n}-1$ 之间的整数。而且，俱乐部里没有两人的看法完全相同。

今天，俱乐部又一次聚会，$m$ 名成员到场，每人已在传统圆桌旁选好了座位。现在，他们要讨论一个万众期待的非常重要的话题。为了充分准备，大家决定分成两个小组，先在组内讨论。为了避免混乱，每个小组必须由圆桌上连续座位的成员组成。同时，为了讨论的全面性，每个小组需涵盖所有观点，也就是说，对于每个基本问题及其两种答案，如果一组里有人持某种看法，另一组里也必须有人持同样看法。

请你写一个程序，算出可以将这些成员分成两个小组的方法有多少种。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$n \geq 2$，$m \geq 3$），分别表示基本问题的数量和参加聚会的成员人数。

第二行包含 $m$ 个互不相同的整数，范围在 $0$ 到 $2^{n}-1$ 之间，按圆桌顺序表示每位成员的看法。

输出格式

输出一个整数，表示将成员分成满足条件的两个小组的方法的数量。

样例

输入

4 5
1 10 0 11 3

输出

2

有两种正确分组方式：
$1\ 10 \mid 0\ 11\ 3$ 和 $3\ 1\ 10 \mid 0\ 11$。

附加样例

• $n=5$，$m=6$，答案为 $4$；
• 一个小样例，答案为 $0$；
• $n=20$，$m=2^{n}$，成员按升序排列，答案很大。

数据范围与提示

详细子任务附加限制及分值如下表所示。