数据前缀：borealis。

不要相信标题！

题目描述

给定 $n$ 行 $m$ 列的网格，每个格子可放置一颗宝石或留空。求使得每一行、每一列都至少有一颗宝石的放置方案数，对 $1\,000\,000\,007$ 取模。

输入格式

本题包含多组测试数据。

第一行一个整数 $T$（$1\le T\le 10^4$），表示测试用例数。

接下来 $T$ 行，每行两个整数 $n,m$（$1\le n,m\le 10^6$）。

保证 $\sum m \le 3.95 \times 10^6$，$\sum n \le 3.95 \times 10^6$（单文件内所有测试用例之和）。

输出格式

对每组测试用例输出一行一个整数，表示方案数对 $1\,000\,000\,007$ 取模的结果。

输入输出样例

样例 #1

样例输入 #1

3
2 2
2 3
5 5

样例输出 #1

7
25
24997921

样例 #2

样例输入 #2

3
1 1
2 2
3 3

样例输出 #2

1
7
265

样例 #3

样例输入 #3

4
1 1
1 5
5 1
2 3

样例输出 #3

1
1
1
25

样例 #4

样例输入 #4

18
1 1000000
1000000 1
2 999983
999983 2
3 300007
300007 3
4 200003
200003 4
5 123457
123457 5
80 400
400 80
99991 100003
100003 99991
100000 100000
131071 131072
131072 131071
200000 200000

样例输出 #4

1
1
750768686
750768686
184028760
184028760
190256799
190256799
412335914
412335914
594177708
594177708
538307143
538307143
513436221
439317439
439317439
422640231

数据范围

• $1\le T\le 10^4$，$1\le n,m\le 10^6$，$\sum m \le 3.95 \times 10^6$，$\sum n \le 3.95 \times 10^6$。
• 本题共 $100$ 个测试点。

$$ \begin{array}{|c|l|} \hline \text{测试点} & \text{性质} \\ \hline 1\sim16 & T \le 5 \text{ 且 }n,m\le 4 \\ 17\sim50 & T \le 5 \text{ 且 }n,m\le 11 \\ 51\sim58 & n=1\text{ 或 }m=1 \\ 59\sim65 & n=m \\ 66\sim80 & n,m \le 80 \text{ 且 }\sum n,\sum m \le 100 \\ 81\sim90 & n,m \le 400 \text{ 且 }\sum n,\sum m \le 600\\ 91\sim100 & n,m \le 10^6 \\ \hline \end{array} $$

背景（与题目没有任何关系）

更妙的是，有些性质就单独占一个测试点，比如那个“P 分块有序”，就一个点，孤零零地待在表格中间，既没有解释什么叫“分块有序”，也没有给具体范围，神秘感直接拉满。我盯着它看了整整十秒，满脑子都在想：这到底是个什么东西？是不是我写了就能过，不写就过不了？最后我决定放弃思考，因为后面还有一整排 N≤0.2、T=200!（感叹号不是表示强烈感情）的一般排列测试点等着我去数，整整 46 个点全是重复的，这种力度，充分体现了出题人对“一般排列”的深切关怀，简直是在用测试点数量告诉我：“别怕，写个暴力，前几十个点稳了。” 时间给到 30 秒，空间给到 1024 MB，慷慨得像是怕我代码写得太烂跑不动，又像是暗示正解复杂度不低。可再看看那些 N≤10、N≤100 的小数据点，我又陷入了深深的纠结：我是该认真想想正解，还是干脆写个暴力把前几十个点骗完就走？出题人用这张表格，成功地把我从“解题模式”切换到了“策略模式”，满脑子都是“这个点我能过吗”“那个性质我能用吗”，题目本身反而成了背景板。 总之，感谢出题人，感谢这套题的测试点表格。它让我在考场上不再迷茫——我知道自己肯定过不了最后那几个大点，但我至少能把表格里的数字背下来，回家也好跟同学吹嘘：“这套题有 400 个测试点，我见过！”

神犇神犇，mod 1e9+9 是什么意思

贡献说明

OpenAI Codex 协助落实数据范围调整，同步修改标准程序、数据生成器和输入验证器，增强正式数据与样例，并完成答案核对、运行计时及测评数据包校验。