B4338 [中山市赛 2023] 组合数问题

众所周知，骐度空间·莫羯座·十一月的萧彰同学擅长计算，尤其擅长计算组合数。 定义组合数 $\binom{i}{j}=\begin{cases}\frac{i!}{j!(i-j)!}&i\ge j\ge 0\\0&其他情况\end{cases}$，可以证明对于任意 $i,j$，$\binom{i}{j}$ 总是整数。 这天，骐度空间·莫羯座·十一月的萧彰遇到了一道难题。有一个 $n\times n$ 的矩阵，$(i,j)$ 表示第 $i$ 行第 $j$ 列，有 $Q$ 次操作，每次操作给定子矩阵的两个端点（分别为 $(x1,y1)$ 和 $(x2,y2)$），对于所有原矩阵中的所有位置 $(x,y)$ 满足 $x1\le x\le x2$，$y1\le y\le y2$ 加上 $\binom{x-x1}{y-y1}$。 骐度空间·莫羯座·十一月的萧彰凭借超强的能力在 $0.0001s$ 内算出了答案，但他想考考你，顺便帮忙验证一下。 骐度空间·莫羯座·十一月的萧彰想知道最后的矩阵长什么样，由于数很大，为了方便，每个位置的值都要对 $10^9 + 7$ 取模。 然而输出量很大，骐度空间·莫羯座·十一月的萧彰无法快速比较这是否是正确答案，所以你只需要输出每一行的异或和和每一列的异或和即可。 骐度空间·莫羯座·十一月的萧彰担心你不知道什么是异或运算，所以他直接给你的输出答案的模板： ```cpp int ans[5010][5010];//假设这是最终的答案矩阵 void print(){ for(int i=1;i

第一行两个正整数 $n$，$Q$。 接下来 $Q$ 行，每行四个正整数 $x1, y1, x2, y2$，表示每次操作的子矩阵的两个端点。

第一行 $n$ 个数，第 $i$ 个数表示最终矩阵第 $i$ 行的异或和。 第二行 $n$ 个数，第 $i$ 个数表示最终矩阵第 $i$ 列的异或和。

### 样例解释 1 最终的矩阵如下： ``` 1 0 1 1 1 1 1 2 1 ``` ### 样例解释 2 最终的矩阵如下： ``` 1 1 0 0 0 1 3 1 0 0 1 4 4 1 0 0 2 5 4 1 0 2 7 9 4 ``` ### 数据范围 对于 $10\%$ 的数据，满足 $1 \le n, Q \le 10$。 对于 $30\%$ 的数据，满足 $1 \le n, Q \le 100$。 对于 $40\%$ 的数据，满足 $1 \le n, Q \le 500$。 对于另外 $20\%$ 的数据，满足所有操作的 $x2, y2$ 均等于 $n$。 对于 $100\%$ 的数据，满足 $1 \le n, Q \le 5000$。 对于所有数据 $1 \le x1 \le x2 \le n, 1 \le y1 \le y2 \le n$。