Transforming data into some other data is typical of a programming job. This problem is about a particular kind of transformation which we'll call the max transform.

Let be a zero-indexed array of integers. For , let denote the subarray of from index to index , inclusive.

Let's define the max transform of as the array obtained by the following procedure:

• Let be a list, initially empty.
• For from to :
  • For from to :
    • Let .
    • Append to the end of .
• Return .

The returned array is defined as the max transform of . We denote it by .

Complete the function solve that takes an integer array as input.

Given an array , find the sum of the elements of , i.e., the max transform of the max transform of . Since the answer may be very large, only find it modulo .