#P18737. [正睿NOI2021训练] 矩阵的秩

[正睿NOI2021训练] 矩阵的秩

矩阵的秩

在有限域 F2\mathbb F_2 中,加法和乘法都按模 22 进行运算。

一个矩阵的秩,是它能选出的线性无关行向量的最大数量。向量组线性无关,指其中不存在非空子集,其向量和为零向量。

给定 n,mn,m,求 F2\mathbb F_2 上所有 n×nn\times n 矩阵中,秩恰为 mm 的矩阵数量,对 109+710^9+7 取模。

输入格式

第一行一个正整数 TT。接下来 TT 行,每行两个正整数 n,mn,m。

输出格式

输出 TT 行,每行一个整数,表示对应的矩阵数量模 109+710^9+7 的结果。

数据范围

1≤T≤1051\le T\le10^5,1≤m≤n≤1071\le m\le n\le10^7。

样例 1

输入

3
3 1
3 2
3 3

输出

49

294

168