题目背景

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}$ 取模后的结果。

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

32

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

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$。