You are given a matrix of length and width . There is exactly one blocked cell in a matrix that is uniformly chosen among all points except and .
Find the expected number of paths from to . You can only move rightwards and downwards. If the expected number of paths is in the simplest form, then print modulo where is the multiplicative inverse of modulo .
Input format
Output format
For each test case, print a single line containing one integer modulo where is the expected number of paths.
When cell is blocked there is exactly one path from to .
When cell is blocked there is exactly one path from to .
Therefore, expected number of path is 1.