This page is still under construction.

Parts of this page are still being built. What you see may change.

Fancy Fence

Time limit1sMemory limit32 MB

Summary
Count axis-aligned integer rectangles lying on a histogram of N sections with heights h_i and widths w_i, modulo 1e9+7.
Level

Hard8 of 10

Topics
Stack, Divide and conquer, Math, Combinatorics
Solved
No attempts yet

Problem

Everybody knows that Balázs has the fanciest fence in the whole town. It is built up from N fancy sections. The sections are rectangles standing closely next to each other on the ground. The ith section has integer height hi and integer width wi.

We are looking for fancy rectangles on this fancy fence.

A rectangle is fancy if:

  • its sides are either horizontal or vertical and have integer lengths
  • the distance between the rectangle and the ground is integer
  • the distance between the rectangle and the left side of the first section is integer
  • it lies completely on sections

What is the number of fancy rectangles?

This number can be very big, so we are interested in it modulo 109 + 7.

Input

The first line contains N, the number of sections.

The second line contains N space-separated integers, the ith number is hi.

The third line contains N space-separated integers, the ith number is wi.

Output

You should print a single integer, the number of fancy rectangles modulo 109 + 7. So the output range is 0, 1, 2, . . . , 109 + 6.

Constraints

  • 1 ≤ N ≤ 105
  • 1 ≤ hi, wi ≤ 109

Hint

There are 5 fancy rectangles of shape:

There are 3 fancy rectangles of shape:

There is 1 fancy rectangle of shape:

There are 2 fancy rectangles of shape:

There is 1 fancy rectangle of shape:

Examples1

  1. Example 1

    Input
    2
1 2
1 2
    Expected output
    12