Central-European Olympiad in Informatics, CEOI 2020, Day 1 (IOI, Unofficial Mirror Contest, Unrated) |
---|

Finished |

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Fancy Fence

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputEverybody 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 $$$i$$$th 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

Input

The first line contains $$$N$$$ ($$$1\leq N \leq 10^{5}$$$) – the number of sections. The second line contains $$$N$$$ space-separated integers, the $$$i$$$th number is $$$h_i$$$ ($$$1 \leq h_i \leq 10^{9}$$$). The third line contains $$$N$$$ space-separated integers, the $$$i$$$th number is $$$w_i$$$ ($$$1 \leq w_i \leq 10^{9}$$$).

Output

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

Scoring

Example

Input

2 1 2 1 2

Output

12

Note

The fence looks like this:

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:

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2021 07:36:52 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|