19679번 - Fancy Fence 서브태스크다국어

문제

Everybody knows that Balázs has the fanciest fence in the whole town. It’s 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 h_i and integer width w_i.

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’s lying completely on sections

What is the number of fancy rectangles?

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

입력

The first line contains N, the number of sections.

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

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

출력

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

제한

• 1 ≤ N ≤ 10⁵
• 1 ≤ h_i, w_i ≤ 10⁹

서브태스크

힌트

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: