题目描述

stjean在玩一个寻宝游戏，他在一个n×m的地图上，起始在(1,1)，现在他想去(n, m)
这个地图上每个格子都会有一个价值 a_ij 的宝物，每次到达一个格子，他会捡起宝物
现在他想知道，如果每次只能 由(x, y) -> (x, y + 1) 或者 (x, y) -> (x + 1, y)
当他走到(n, m)时，手中宝物总价值为k的方案数有多少种？

文件输入

第一行n和m和k
下面n行，每行m个数

文件输出

输出方案数

输入样例

2  2  6    
2  1
1  3

输出样例

2

数据规模

对于所有的数据，k在long long 范围内
对于20%的数据，n,m <= 3    a_ij <= 10
对于20%的数据，n,m <= 12   a_ij <= 1000
对于20%的数据，n,m <= 20   a_ij <= 10
对于40%的数据，n,m <= 20  a_ij <= 1000000000