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