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