Consider the same situation as the previous problem. We have a city whose streets are defined by an X × Y grid. We are interested in walking from the upper left-hand corner of the grid to the lower right-hand corner. We are given an X × Y matrix BAD, where BAD[i,j] = "yes" if and only if the intersection between streets i and j is somewhere we want to avoid. If there were no bad neighborhoods to contend with, the shortest path across the grid would have length (X - 1) + (Y - 1) blocks, and indeed there would be many such paths across the grid. Each path would consist of only rightward and downward moves. Give an algorithm that takes the array BAD and returns the number of safe paths of length X + Y - 2. For full credit, your algorithm must run in O(XY ).