悟道
题号:NC229815
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
Special Judge, 64bit IO Format: %lld

题目描述

本题有特殊的空间限制。

元婴大能贪图恶堕的魔法少女美色,强行进行双修,企图悟出算法大道。为此,他们正在进行一个小小的游戏。

具体来说,元婴大能创造了一个 的四维坐标空间,并在其中一个坐标放置一个异果。两人交替进行操作,元婴大能先手,每次可以将异果沿一个维度向小的方向移动,如果这一维的坐标是 1 则不能选择这一维,无法移动的一方会输掉游戏,另一方取得胜利。

受到界外星海的影响,m 个坐标被虚空覆盖,异果初始不能被放置在这些坐标上,移动过程中不能停留在这些坐标上,也不能越过这些坐标。例如在没有坐标被虚空覆盖的情况下可以从 (1,2,3,4) 移动到 (1,2,3,2),但是如果 (1,2,3,3) 被虚空覆盖,那么就不能从 (1,2,3,4) 移动到 (1,2,3,2)

形式化地说,设 m 个被虚空覆盖的坐标组成的集合为 S,假设当前异果位于 (x_1,x_2,x_3,x_4),那么一次操作如下:
将恰好一个 x_i () 变为 x_i',其中 ,且不存在 满足:


五百年寿元将至,元婴大能不希望陨落于算法之元神劫,因此他不想浪费太多时间玩这个游戏,希望你帮他算一算,有多少个未被虚空覆盖的坐标,初始时将异果放置在这里,如果双方都采取最优策略,元婴大能可以获胜。

输入描述:

第一行两个以空格分隔的整数 n,m (),表示空间每个维度的大小和被虚空覆盖的坐标的数量。

接下来 m 行,每行四个以空格分隔的正整数 (),表示第 i 个被虚空覆盖的坐标。

保证任意两个被虚空覆盖的坐标不相同,也就是说

输出描述:

一个非负整数,表示有多少个未被虚空覆盖的坐标满足初始时将异果放置在这里,如果双方都采取最优策略,元婴大能可以获胜。
示例1

输入

复制
2 0

输出

复制
8

说明

第一个样例中,符合条件的坐标集合为 \{(1,1,1,2),(1,1,2,1),(1,2,1,1),(1,2,2,2),(2,1,1,1),(2,1,2,2),(2,2,1,2),(2,2,2,1)\}
示例2

输入

复制
2 2
1 1 1 1
2 2 2 2

输出

复制
6

说明

第二个样例中,符合条件的坐标集合为 \{(1,1,2,2),(1,2,1,2),(1,2,2,1),(2,1,1,2),(2,1,2,1),(2,2,1,1)\}
示例3

输入

复制
37 0

输出

复制
1836504
示例4

输入

复制
73 3
1 1 4 5
1 4 1 1
4 5 1 4

输出

复制
28065919