Forgot Password ?
New password will be sent to following email id
Number of Paths 2
Problem Code : PATH2
3 2 2 1 1 2 2 2 2 1 2 2 1 3 3 1 2 2
1 0 2
Time Limit :
C , C++ , Java , Python 2
Login to submit your response.
Given a grid of dimensions <b>N × M</b>. Some <b>K</b> cells of the grid are blocked and no one is allowed to move through these cells. Buddy is standing at location <b>(1, 1)</b> (top most left corner) and he needs to reach at location <b>(N, M)</b> (bottom most right corner). If Buddy's current location is <b>(i, j)</b> then he is allowed to move either in right direction, i.e. <b>(i, j+1)</b>, or in down direction, i.e. <b>(i+1, j)</b> if and only if those cells are not blocked. Buddy is not allowed to move outside the grid. Print total number of ways in which Buddy can reach at location <b>(N, M)</b> modulo 10<sup>9</sup>+7.
First line contains an integer integer <b>T</b> denoting number of test cases.<br> First line of each test case contains three integers <b>N</b>, <b>M</b> and <b>K</b> respectively.<br> Each of the next <b>K</b> line contains two integers <b>X</b> and <b>Y</b> denoting the cell location which is blocked.
For each test case print required answer in new line.
1 ≤ <b>T</b> ≤ 20<br> 1 ≤ <b>N, M</b> ≤ 2000<br> 1 ≤ <b>K</b> ≤ 1000<br> 1 ≤ <b>X</b> ≤ <b>N</b><br> 1 ≤ <b>Y</b> ≤ <b>M</b><br>