## COCI '18 Contest 6 #5 Mobitel

View as PDF

Points: 20 (partial)
Time limit: 6.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 . 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 ?

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 .

#### Input

In the first line there are integer numbers and .

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

#### Output

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

#### Scoring

In the test samples totally worth 20% of the points it will hold .

In the test samples totally worth 20% of the points it will hold , and all the numbers in the table will be less than or equal to .

In the test samples totally worth additional 30% it will hold .

#### Sample Input 1

2 3 200
2 3 4
5 6 7

#### Sample Output 1

2

#### Explanation for Sample Output 1

There are three possible ways:

• - total product
• - total product
• - total product

#### Sample Input 2

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

#### Sample Output 2

3

#### Sample Input 3

2 5 3000
1 2 3 4 5
6 7 8 9 10

#### Sample Output 3

3