Given a table composed of N x M cells, each containing some number of gold coins. You start from the upper left hand corner and at each step may go down or to the right. At each step you collect all the coins that are in that location. Find the maximum number of coins you can collect and the path that provides that result.

(a) If we were to use a Brute force method to solve this problem, we would need to explore all possible paths. Find the exact number of paths that exist. Explain your answer. (Note that each path must contain exactly N - 1 right moves and M - 1 down moves. Try thinking of the path as a strings and figure out how many ways that string can be rearranged.)

(b) Give a dynamic programming algorithm that solves this problem using O(NM) time and space.