题目描述

彩球布置完毕，暮色也渐渐落入森林。通往会场的长廊还未点灯，大笨龙与聪明兔便带上储能装置，前往一片方格形的魔法庭院。他们需要在穿过庭院的途中获取足够的能量，让长廊赶在来宾抵达前亮起。

庭院共有 $r$ 行 $c$ 列，第 $i$ 行第 $j$ 列的格子上写着一个正整数 $a_{i,j}$。他们从左上角的格子 $(1, 1)$ 出发，前往右下角的格子 $(r, c)$，每一步只能向右或向下移动一格，且不能离开庭院。

一条路径的能量值等于这条路径上所有格子中的数字之积，包含起点和终点的数字。请你求出能量值大于等于 $n$ 的路径数量。

只要两条路径经过的格子序列不同，就视为不同的路径。答案可能很大，请输出答案对 $10^9 + 7$ 取模后的结果。

输入格式

从文件 grid.in 中读入数据。

第一行包含三个整数 $r, c, n$，依次表示庭院的行数、列数和能量门槛。

接下来 $r$ 行，每行包含 $c$ 个正整数，其中第 $i$ 行第 $j$ 个整数为 $a_{i,j}$。

输出格式

输出到文件 grid.out 中。

输出一行一个整数，表示能量值大于等于 $n$ 的路径数量对 $10^9 + 7$ 取模后的结果。

样例 1

2 3 200
2 3 4
5 6 7

2

样例1解释

三条路径的能量值分别为 $2 \times 3 \times 4 \times 7 = 168$、$2 \times 3 \times 6 \times 7 = 252$ 和 $2 \times 5 \times 6 \times 7 = 420$，其中两条达到门槛 $200$。

样例 2

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

3

样例2解释

经过格子 $(2, 1)$ 的路径能量值均为 $90$，这样的路径共有 $3$ 条；其余路径的能量值均为 $2$。

样例3

见附件中的 grid3.in 与 grid3.ans。

样例4

见附件中的 grid4.in 与 grid4.ans。

数据范围

对于所有数据，$1 \le r, c \le 300$，$1 \le n \le 10^6$，$1 \le a_{i,j} \le 10^6$。

本题共有 $20$ 个测试点，每个测试点 $5$ 分。

测试点编号	$r, c \le$	$n \le$	特殊性质
$1 \sim 2$	$10$	$10^6$	无
$3 \sim 4$	$300$
$5 \sim 8$	$100$	$10^6$	A
$9 \sim 11$	$300$		B
$12 \sim 14$	$100$		无
$15 \sim 20$	$300$

特殊性质 A：所有格子中的数均小于 $10$。

特殊性质 B：所有格子中的数均为 $2$ 的非负整数次幂，即 $a_{i,j} = 2^{e_{i,j}}$，其中 $e_{i,j}$ 为非负整数。

样例附件

下载全部样例（grid-samples.zip）