#3468. 滑雪

内存限制:256 MiB 时间限制:30 Sec

题目描述

陶陶最近迷上了滑雪,这天他来到了滑雪场。滑雪场可以看做N*M 的方格区域,每个格子有一个高度,陶陶可以选择任意一个格子作为起点,然后每次可以滑到相邻的某个格子,但要满足经过格子的高度严格递减,同时陶陶可以随时停下来,途中滑的次数就为这条滑雪路径的长度,例如经过了3个格子,路径长度为就为2。有一点需要注意,陶陶不能够停在原地,也就是说路径的长度一定是正整数。

这样的话,陶陶就有很多很多种路径选择,但能发现不可能有无限种路径供陶陶选择,然后陶陶就想知道所有可能路径长度的0K次方之和为多少。由于答案可能会很大,你只需要输出每个答案Mod 12345后的值。

 

输入格式

N+1行。

第一行包含三个正整数N,M,K

接下来有N行,每行包含M个不超过10^9的正整数,依次表示每个格子的高度。

 

输出格式

K+1行,每行包含一个非负整数,第i行的整数表示所有可能路径长度的i-1 次方之和Mod 12345后的值。

样例

样例输入


			
3 4 3
1 2 3 4
4 3 2 1
1 2 3 4

样例输出


			
38
66
136
318

数据范围与提示



NM<=300,K<=200