题目描述

给定一个 $r$ 行 $c$ 列的方格，第 $i$ 行第 $j$ 列的格子中有一个正整数 $a_{i,j}$。

从左上角走到右下角，每次只能向右或向下移动一格。求经过的格子中的数字之积大于等于 $n$ 的路径方案数。

路径经过的格子包括起点和终点；当 $r=c=1$ 时，仅经过该格子的路径也计为一种方案。

答案对 $10^9+7$ 取模。

输入格式

从文件 mobitel.in 中读取数据。

第一行包含三个整数 $r,c,n$，分别表示行数、列数和乘积阈值。

接下来 $r$ 行，每行包含 $c$ 个正整数，第 $i$ 行的第 $j$ 个数表示 $a_{i,j}$。

输出格式

将结果输出到文件 mobitel.out 中。

输出一行一个整数，表示乘积大于等于 $n$ 的路径方案数对 $10^9+7$ 取模的结果。

样例

2 3 200
2 3 4
5 6 7

2

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

3

数据范围

对于全部数据，$1\leq r,c\leq 300$，$1\leq n\leq 10^6$，$1\leq a_{i,j}\leq 10^6$，且 $a_{i,j}$ 为整数。