634. Sum of subarray minimum

0

Medium

Rohit wants to solve a subarray problem. So he picks a problem and stucks in it . He needed your help in this problem.
You are given an array of integers ***nums*** of size **n**.
Find the sum of min(b), where b ranges over every (contiguous) subarray of **nums**.
Since the answer may be large, Print the answer modulo 10

^{9}+ 7.Input Format

First line contains an integer N(size of array) .

Second line contains an integer array.

Second line contains an integer array.

Output Format

Print the answer.

Example

Input

4
3 1 2 4

Output

17

Constraints

1 <= n <= 10

1 <= nums[i] <= 10

^{4}1 <= nums[i] <= 10

^{4}Loading...

View Submissions

Console