P12772 [POI 2018/2019 R1] 俱乐部成员 2 Club members 2

翻译来自于 [LibreOJ](https://loj.ac/p/4918)。

**题目译自 [XXVI Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi26-1/dashboard/) [Klubowicze 2](https://sio2.mimuw.edu.pl/c/oi26-1/p/klu/)** 我们再次来到了字节克讨论俱乐部。这个俱乐部有 $2^{n}$ 名成员，每人都对 $n$ 个基本问题表达了自己的看法。这些问题的具体内容不重要，只需知道每个问题都有两种答案可选。每个人的看法可以用一串二进制位表示，转化为十进制后是 $0$ 到 $2^{n}-1$ 之间的整数。而且，俱乐部里没有两人的看法完全相同。 今天，俱乐部又一次聚会，$m$ 名成员到场，每人已在传统圆桌旁选好了座位。现在，他们要讨论一个万众期待的非常重要的话题。为了充分准备，大家决定分成两个小组，先在组内讨论。为了避免混乱，每个小组必须由圆桌上连续座位的成员组成。同时，为了讨论的全面性，每个小组需涵盖所有观点，也就是说，对于每个基本问题及其两种答案，如果一组里有人持某种看法，另一组里也必须有人持同样看法。 请你写一个程序，算出可以将这些成员分成两个小组的方法有多少种。

输入的第一行包含两个整数 $n$ 和 $m$ $(n \geq 2, m \geq 3)$，分别表示基本问题的数量和参加聚会的成员人数。 第二行包含 $m$ 个互不相同的整数，范围在 $0$ 到 $2^{n}-1$ 之间，按圆桌顺序表示每位成员的看法。

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

**样例 1 解释** 有两种正确分组方式：$1 10 \mid 0 11 3$ 和 $3 1 10 \mid 0 11$。 **附加样例** 1. $n=5, m=6$，答案为 $4$； 2. 一个小样例，答案为 $0$； 3. $n=20, m=2^{n}$，成员按升序排列，答案很大。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 15, m \leq \min(2^{n}, 100)$ | $15$ | | $2$ | $n \leq 15, m \leq \min(2^{n}, 5000)$ | $20$ | | $3$ | $n \leq 30, m \leq \min(2^{n}, 100000)$ | $45$ | | $4$ | $n \leq 30, m \leq \min(2^{n}, 2000000)$ | $20$ |