모비텔

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

요약

R×S 격자의 왼쪽 위에서 오른쪽 아래까지 오른쪽이나 아래로만 움직이는 경로 중, 지나는 칸 값의 곱이 N 이상인 경로의 수를 10^9+7로 나눈 나머지로 구합니다.

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

문제

작은 니콜라는 최근 구구단을 배웠다. 학습을 이어 가려고 그는 다음 과제를 생각해 냈다. 그는 $R \times S$ 크기의 표를 만들고 각 칸에 정수를 하나씩 적었다. 그리고 왼쪽 위 칸에서 오른쪽 아래 칸까지 한 번에 오른쪽 또는 아래로 한 칸씩 이동하는 경로 중, 경로에 포함된 모든 칸(시작 칸과 끝 칸 포함)에 적힌 수의 곱이 $N$ 이상인 경로가 몇 가지인지 물었다. 지금 그에게는 시간이 없어서 여러분에게 도움을 청했다. 답이 매우 클 수 있으므로 $10^9 + 7$ 로 나눈 나머지를 출력한다.

입력

첫 줄에 정수 $R$ , $S$ ( $1 \le R, S \le 300$ )와 $N$ ( $1 \le N \le 10^6$ )이 주어진다. 다음 $R$ 개 줄에는 각각 $S$ 개의 정수가 주어지며, 이는 각 칸에 적힌 수로 모두 1 이상 $10^6$ 이하이다.

출력

조건을 만족하는 경로의 수를 $10^9 + 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
```