题目描述

给出一个$R\times S$的数字矩阵和一个常数N，求所有从左上角到右下角的满足下列条件的路径数：

1. 每步可以从某个格子走到它正右方或正下方的格子。
2. 把经过的所有格子（包括起点和终点，共有$(R+S-1)$个）上的数相乘，得到的结果不小于$N$。

答案对$1000000007$取模。

输入格式

输入共$(R+1)$行。

第一行有三个整数$R,S,N$。

接下来$R$行，每行有$S$个正整数（每个正整数$x$都满足$1\le x\le 10^{6}$），描述数字矩阵。

输出格式

输出共$1$行，表示答案。请对$1000000007$取模。

样例数据

样例1

样例输入1

2 3 200
2 3 4
5 6 7

样例输出1

2

样例2

样例输入2

3 3 90
2 1 1
45 1 1
1 1 1

样例输出2

3

样例3

样例输入3

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

样例输出3

3

数据范围与约定

对于$20\%$的数据，满足$N\le 300$。

对于$20\%$的数据，满足$R,S \le 100,x \le 10$。

对于另外$30\%$的数据，满足$R,S \le 100$。

对于$100\%$的数据，满足$1\le R,S \le 300,1\le x,N\le 10^6$。

时空限制：每个测试点$5\text{s} \ 64\text{MB}$。

样例解释

样例$1$解释：有三条可能的路径。

1. $2\rightarrow 3\rightarrow 4\rightarrow 7,\Pi=168$

2. $2\rightarrow 3\rightarrow 6\rightarrow 7,\Pi=252$

3. $2\rightarrow 5\rightarrow 6\rightarrow 7,\Pi=420$.