## Expected Value

View as PDF

Points: 15
Time limit: 0.6s
Memory limit: 1G

Problem types
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

Shinmyoumaru has gotten out of bed and needs to go fetch the Miracle Mallet. To do this, she needs to travel from the top-left corner of an grid to the bottom-right corner.

With probability , Shinmyoumaru will be facing to the right, and with probability , she will be facing down. She will take a single step, and then with probability , she will swap the direction she is facing from either right to down, or from down to right. If her next step would take her off of the grid, she will reorient herself forcibly in the direction of the bottom-right corner.

The square in row and column of the grid has inchlings. Shinmyoumaru wants to know how many inchlings she will visit in expectation on her trip.

#### Input Specification

The first line contains two space-separated positive integers, and . .

The next line contains a single positive integer, .

The next lines contain space-separated integers, the values in row-major order.

#### Output Specification

Let be the expected number of inchlings that she will encounter on her trip, where and are relatively prime positive integers. Output .

#### Sample Input

1 2
2
1 2
3 4

#### Sample Output

499122184