1 Silver Gathering Given a table composed of NM cells, each containing some number of silver 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) [10 points] 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 N1 right moves and M1 down moves. Try thinking of the path as a strings and figure out how many ways that string can be rearranged.) (b) [15 points] Give a dynamic programming algorithm that solves this problem using O(NM) time and space. Implement this in the language of your choice and include your code in this document and submit the source code file