「CZOI-R1」卡牌

题目背景

Alice 和 Bob 正在玩卡牌游戏。

题目描述

每张卡牌有四个属性:攻击、防御、速度、血量。 我们称一张卡牌能胜过另一张卡牌,当且仅当其至少有三个属性都大于另一张卡牌。 Bob 拥有 $m$ 张卡牌,而 Alice 拥有每个属性值在 $[1, n]$ 的所有 $n^4$ 张卡牌。 现在 Alice 想知道:她有多少张卡牌可以胜过所有 Bob 的卡牌?

输入输出格式

输入格式


第一行包含两个整数 $n, m$,分别表示属性值上限和 Bob 的卡牌数量。 接下来 $m$ 行,每行四个整数 $a_i, b_i, c_i, d_i$,表示 Bob 一张卡牌的属性。

输出格式


输出一行一个整数,表示答案对 $2^{32}$ 取模后的结果。

输入输出样例

输入样例 #1

5 5
2 2 1 2
3 4 2 4
4 3 2 2
1 4 2 3
1 2 4 4

输出样例 #1

32

输入样例 #2

10 10
7 8 5 2
5 9 9 4
3 8 4 3
5 6 5 1
5 5 2 4
9 5 5 1
3 7 2 5
4 4 5 4
9 6 1 5
3 7 3 7

输出样例 #2

243

说明

**【数据范围】** **本题采用捆绑测试**。 - Subtask #1($10\text{ pts}$):$n, m \le 50$。 - Subtask #2($10\text{ pts}$):$n, m \le 5 \times 10^3$。 - Subtask #3($20\text{ pts}$):$d_i = 1$。 - Subtask #4($20\text{ pts}$):$n, m \le 10^5$。 - Subtask #5($40\text{ pts}$):无特殊限制。 对于所有测试数据,$1 \le n, m \le 5 \times 10^5$,$1 \le a_i, b_i, c_i, d_i \le n$。