The input to the problelm is a string Z-ZIZ Zn where each {1, 2, ,9) and an integer k where 0 k n. An example string is Z-8473817, which is of length n-7. We want to insert k multiplication operators into the string so that the mathematical result of the expression is the largest possible. There are n -1 possible locations for the operators, namely, after the i-th character where i,,n-1. For example, for input Z-21322 and k-2, then one possible way to insert the operators is: 2 1 322-644, another possibility is 21 x 3 x 22 1386. Design a dynamic programming to output the maximum product obtainable from inserting exactly k mul tiplication operators x into the string. For simplicity, you can assume that all table entries use (1) space and that all the multiplication operations in your algorithm take O(1) time