4003. 洛希的极限

【题目背景】

在此键入。

【题目描述】

有一个n*m的网格，S只能在某个格子的正中间，他可以从一个格子（x0,y0）跳到另一个格子（x1,y1），需满足x0<x1且y0<y1；

此外，还有一些限制区域，这些区域可以看作q个矩形，每一个矩形覆盖一片网格；

对于每一次跳跃，S能够从（x0,y0）跳到（x1,y1），除了满足x0<x1且y0<y1，还必须存在一个矩形同时包含（x0,y0）和（x1,y1），S想经过尽量多的不同的网格；

给出n,m,q以及q个矩形，问S最多可以经过多少个网格，以及经过这么多网格的方案数。

注意：开始的时候S可以随意选择一个落点（x,y），1≤x≤n，1≤y≤m；

对于两种方案，它们被视为是不同的，当且仅当存在一个网格，它在其中一种方案中出现了，但没有在另一种方案中出现。

【输入格式】

第一行一个正整数T表示数据组数；

对于每组数据，第一行三个整数n,m和q。

接下来q行，每行四个整数r1,c1,r2,c2(1≤r1≤r2≤n，1≤c1≤c2≤m)，表示一个矩形，这个矩形包含所有满足r1≤r≤r2，c1≤c≤c2的网格(r,c)。

【输出格式】

对于每组数据，输出一行，两个整数，分别表示S最多经过多少个网格以及经过这么多网格的方案数，由于方案数可能很大，方案数请对10^9+7取模后再输出。

【样例输入】

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

【样例输出】

3 2
3 1

【样例说明】

第一组数据中：共有两种经过三个网格的方案：(1,1)-(2,2)-(3,3)和(1,1)-(2,2)-(3,4)。
第二组数据中：只有一种经过三个网格的方案：(1,1)-(2,2)-(3,3)。

【数据规模与约定】

【来源】

2019.4.18