P7245 灯光效果

  「为了你唱下去——直到荒芜」   「为了你唱下去——直到……」   舞台上，享受地阖上眼眸，双手交叠扣在话筒，后脚踮起，在随着节奏闪烁变换的灯光下轻摇……   嘴角轻扬，绫珍惜着步入瞳孔的每一粒光，那些从天依的发丝、脸颊划过的，带着属于她的旖旎，轰击着明明做好防备的绫的心尖。   收尾的音调扬起，灯光，也是那样应景呢。

对于舞台效果，灯光是重要的角色。背景屏幕是一个 $n \times n$ 的矩形，行从左到右，列从上到下编号为 $1\sim n$，并用 $(x,y)$ 表示第 $x$ 行第 $y$ 列的灯光单元。 作为御用灯光师的阿绫设计了一个控制背景灯光效果的程序。她设定了两个长度为 $m$ 的**递增**整数序列 $\{x_m\}$ 和 $\{y_m\}$，且满足 $0\le x_1,y_1$，$x_m,y_m\le n$。每次灯光变换，程序会均匀地随机生成两对整数 $(i_1,i_2),(j_1,j_2)$，满足 $1\le i_1

无

无

#### 样例解释 1 样例中，$\{x_m\}=\{y_m\}=\{0,1,2\}$。可以发现，此 $2\times 2$ 矩阵的任意一个子矩阵都可以被变换。当子矩阵大小分别为 $1,2,4$ 时，对应方案数分别为 $4,4,1$，由于只操作一次，所以对应的最终矩阵元素之和分别为 $4\times1,4\times2,1\times 4$。于是，答案为 $\frac{4+8+4}{4+4+1}=\frac{16}9$。 #### 数据规模与约定 **本题采用捆绑测试。** 对于 $100\%$ 的数据，$2\le m\le \min(n+1,10^3)$，$1\le n\le10^9$，$1\le k\le 10^6$，保证 $x_i$ 互不相等且递增，$y_i$ 互不相等且递增。 | 子任务 | 分值 | $n$ | $m$ | $k$ | | :----: | :--: | :----------: | :------: | :----------: | | 1 | 10 | $ \le 4$ | $ \le 3$ | $ \le 2$ | | 2 | 5 | / | $2$ | / | | 3 | 25 | $ \le 10^2 $ | / | $ \le 10^2 $ | | 4 | 20 | $ \le 10^9 $ | / | $ \le 10^2 $ | | 5 | 20 | $ \le 10^2 $ | / | $ \le 10^6 $ | | 6 | 20 | / | / | / | ------------