题目描述

一个 $F$ 阶 FFT 图是一个有向图，共有 $F$ 层，层编号为 $0,1,\ldots,F-1$。

每一层都有 $2^{F-1}$ 个结点，编号为 $0,1,\ldots,2^{F-1}-1$。用 $(h,x)$ 表示第 $h$ 层、编号为 $x$ 的结点。

FFT 图中的有向边如下。对于每个 $0\le h<F-1$ 和每个编号 $x$：

1. 从 $(h,x)$ 向 $(h+1,x)$ 连边；
2. 从 $(h,x)$ 向 $(h+1, x\oplus 2^{F-h-2})$ 连边。

其中 $\oplus$ 表示按位异或。

初始时所有结点都是白色的。后来有 $T$ 个结点被染成了黑色。

请计算有多少个有序对 $(a,b)$ 满足：存在至少一条从 $(0,a)$ 到 $(F-1,b)$ 的有向路径，并且这条路径不经过任何黑色结点。

输入格式

第一行两个整数 $F,T$。

接下来 $T$ 行，每行两个整数 $h,x$，表示结点 $(h,x)$ 被染成黑色。

输出格式

输出一个整数，表示满足条件的有序对 $(a,b)$ 的数量。

数据范围与子任务

• $1\le F\le 30$
• $1\le T\le 100000$
• $A\oplus B$ 表示按位异或。
• 注意：边是有向边，虽然图示中没有画箭头。
• 10 分：$F\le 10$
• 10 分：$F\le 16$
• 30 分：$T\le 2000$

样例输入 1

3 3
0 2
1 1
2 3

样例输出1

5

样例解释

满足条件的 $(a,b)$ 共 5 对，分别为

样例输入2

4 3
0 1
1 1
2 4

样例输出2

44

图示对应这个样例。

样例输入3

15 10
3 12914
8 10479
12 1039
8 13597
11 2633
12 10668
12 6769
11 4443
7 15697
12 13418

样例输出3

268271648