Problem Statement

Amazon Web Services has n servers. The cache optimization power of the i th server is power[i] . The cache optimization power of a group of contiguous servers is defined as Power[l,r] = (min power[i]) * (sum power[i]) where l <= i <= r . Find the sum of Power[l,r] for each possible contiguous group of servers. Since the answer can be very large, return the answer modulo 1000000007 or 10^9 + 7 . Example: power = [2, 3, 2, 1] There are n = 4 servers. The powers of contiguous groups of servers are: Power[0,0] = min([2]) * sum([2]) = 2 * 2 = 4 Power[0,1] = min([2, 3]) * sum([2, 3]) = 2 * 5 = 10 Power[0,2] = min([2, 3, 2]) * sum([2, 3, 2]) = 2 * 7 = 14 Power[0,3] = min([2, 3, 2, 1]) * sum([2, 3, 2, 1]) = 1 * 8 = 8 Power[1,1] = min([3]) * sum([3]) = 3 * 3 = 9 Power[1,2] = min([3, 2]) * sum([3, 2]) = 2 * 5 = 10 Power[1,3] = min([3, 2, 1]) * sum([3, 2, 1]) = 1 * 6 = 6 Power[2,2] = min([2]) * sum([2]) = 2 * 2 = 4 Power[2,3] = min([2, 1]) * sum([2, 1]) = 1 * 3 = 3 Power[3,3] = min([1]) * s