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.
Constraints
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
Copy
1 2
2
1 2
3 4
Sample Output
Copy
499122184
Comments