#P18737. [正睿NOI2021训练] 矩阵的秩
[正睿NOI2021训练] 矩阵的秩
矩阵的秩
在有限域 中,加法和乘法都按模 进行运算。
一个矩阵的秩,是它能选出的线性无关行向量的最大数量。向量组线性无关,指其中不存在非空子集,其向量和为零向量。
给定 ,求 上所有 矩阵中,秩恰为 的矩阵数量,对 取模。
输入格式
第一行一个正整数 。接下来 行,每行两个正整数 。
输出格式
输出 行,每行一个整数,表示对应的矩阵数量模 的结果。
数据范围
,。
样例 1
输入
3
3 1
3 2
3 3
输出
49
294
168