Mobitel

시간 제한6초메모리 제한512 MB

요약

R×S 격자에서 오른쪽과 아래로만 이동하는 경로 중 지나는 칸 값의 곱이 N 이상인 경로 수를 1e9+7로 나눈 나머지를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 행렬
정답자: 아직 제출이 없습니다

문제

Little Nikola has recently learned a multiplication table. To try to continue learning, he came up with the following task.

He made a table of size R×S. In each field of the table he wrote an integer value and asked himself: How many possible ways are there to get from the upper left corner to the lower right corner of the table by moving each step to one field right or down, so that a product of all the numbers on the path (including the initial and the final field) is at least N?

Since currently he has no time, he has asked you for help. Since the required number of ways can be quite large, just print its remainder of division by 109 + 7.

입력

In the first line there are integer numbers R, S (1 ≤ R, S ≤ 300) and N (1 ≤ N ≤ 106).

In the next R lines there are S integer numbers between 1 and 106 which denotes the numbers written in each field of the table.

출력

In the only line print the remainder of the required number of the ways modulo 109 + 7.

예제3

예제 1
입력
```
2 3 200
2 3 4
5 6 7
```
예상 출력
```
2
```
예제 2
입력
```
3 3 90
2 1 1
45 1 1
1 1 1
```
예상 출력
```
3
```
예제 3
입력
```
2 5 3000
1 2 3 4 5
6 7 8 9 10
```
예상 출력
```
3
```