Expected Value

View as PDF

Submit solution

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

Problem types

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 N \times N grid to the bottom-right corner.

With probability p, Shinmyoumaru will be facing to the right, and with probability 1-p, she will be facing down. She will take a single step, and then with probability p, 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 i and column j of the grid has a_{ij} inchlings. Shinmyoumaru wants to know how many inchlings she will visit in expectation on her trip.

Constraints

1 \le A_i < B_i \le 10

2 \le N \le 10^3

1 \le a_{ij} \le 10^3

Input Specification

The first line contains two space-separated positive integers, A_i and B_i. p = \frac{A_i}{B_i}.

The next line contains a single positive integer, N.

The next N lines contain N space-separated integers, the a_{ij} values in row-major order.

Output Specification

Let \frac{P}{Q} be the expected number of inchlings that she will encounter on her trip, where P and Q are relatively prime positive integers. Output P Q^{-1} \pmod{998\,244\,353}.

Sample Input

1 2
2
1 2
3 4

Sample Output

499122184

Comments

There are no comments at the moment.