#P10374. [2021年联测]傅里叶与矩阵
[2021年联测]傅里叶与矩阵
题目描述
有一个 行 列的矩阵,第 列所有格子的权值均为 ,且 两两不同。
每次询问给定行号 。考虑从 到 的所有最短路径,每步向下或向右移动一个格子。一条路径的权值是其经过的所有格子的权值之积,包含起点和终点。
求所有这些路径的权值之和对 取模的结果。
输入格式
第一行三个整数 。第二行 个整数 。接下来 行,每行一个整数 。
输出格式
每次询问输出一行一个整数,表示相应答案。
样例 1
2 3 2
1 3 5
1
2
15
135
样例 2
5 2 5
1 2
1
2
3
4
5
2
6
14
30
62
样例 3
3 3 3
215 228 229
1
2
3
11225580
555879289
157593602
数据范围
- 的数据满足 。
- 另外 的数据满足 。
- 另外 的数据满足 。
- 另外 的数据满足 。
- 剩下 的数据满足 。
- 所有数据满足 ,,,且所有 两两不同。