#12610. 虚空之梦

内存限制:512 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: PaperCloud

题目描述

年 月 日 ,天亮了,而通宵复习期末考的 Barisore 还没放下手中的笔记。

最后,她带着迷茫和困倦,进入了梦乡。

梦境里,她再次来到那间充斥着数学的味道的教室,而此时这里空无一人,摆的整整齐齐的 张桌子,每一张桌子上都留着他曾经努力听课的痕迹。

而此时,这些模糊的记忆都化成了数字出现在她眼前。

有一个 行 列的矩阵,第 行第 列为整数 。

定义一个子矩阵 的回忆值为其中所有数之和的 次方, ,其中 是给定的常数。

注:在本题中,我们规定 。

请计算这个矩阵的所有子矩阵的回忆值之和。

形式化的,请你计算 。

输入格式

第一行三个整数 。

以下 行每行 个整数 。

输出格式

一行一个整数表示答案。由于这个数可能过大,你只需输出其对 取模的值即可。

样例

样例 1 输入

2 3 1
2 8 7
4 5 9

样例 1 输出

236

样例 2 输入

5 7 3
3 4 7 6 9 4 5
5 4 2 9 7 8 4
3 1 9 4 5 2 2
3 8 9 5 6 6 3
5 1 9 4 8 2 6

样例 2 输出

90937097

数据范围与提示

对于全部数据,。

子任务 1( 分):;

子任务 2( 分):;

子任务 3( 分):;

子任务 4( 分):;

子任务 5( 分):;

子任务 6( 分):无特殊限制。

子任务内部有一定梯度。

提示:

  1. 多项式展开,二维前缀和;

  2. 尝试转换求和式。