Mobitel
레이팅 미적용의견: 0
6 \(s / 64\) \(MB / 130\) points
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 10 {9}{ } + 7.
In the test samples totally worth 20% of the points it will hold \(N\) ≤ 300.
In the test samples totally worth 20% of the points it will hold \(R\) , \(S\) ≤ 100, and all the numbers in the
table will be less than or equal to 10.
In the test samples totally worth additional 30% it will hold \(R\) , \(S\) ≤ 100.
In the first line there are integer numbers \(R\) , \(S\) (1 ≤ \(R\) , \(S\) ≤ 300) and \(N\) (1 ≤ \(N\) ≤ 10 {6}{ }).
In the next \(R\) lines there are \(S\) integer numbers between 1 and 10 ^{6} 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 10 {9}{ } + 7.
2 3 200
2 3 4
5 6 7
3 3 90
2 1 1
45 1 1
1 1 1
2 5 3000
1 2 3 4 5
6 7 8 9 10output
output
2
3
3Clarification of the first sample:
There are three possible ways:
●
2->3->4->7
- total product 168
●
2->3->6->7
- total product 252
●
2->5->6->7
- total product 420
6 s / 64 MB / 130 points
평가 및 의견
Mobitel
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Mobitel