You are given $2$ arrays A and B$,$ each of size N$.$

You are now standing at index N and want to move to index $1$ by performing the following operation one or more times until you reach index $1$:

$1.$ Let's say that the element you are currently standing on is i$.$ The cost of standing at index i will be equal to A$[$i$].$

$2.$ Choose index j such that j $$ i

$3.$ If you want to move from index i to index j$,$ the cost of passing between them will be equal to B$[$j$].$

Find the minimum cost to move from index N to index $1.$ Since the answer can be very large, return it modulo $10^9+7$

Input Format

The first line contains an integer, N$.$ denoting the number of elements in A and B$.$

Each line i of the N subsequent lines $($where i N $)$ contains an integer describing A$[$i$].$

Each line i of the N subsequent lines $($where i N $)$ contains an integer describing B$[$i$].$

Input

Constraints

N

A$[$i g

B$[$i

$5551425415165424411143$

Sample Test Cases

Case $1$

Input:

$55514254151$

Output:

$13$

Explanation:

Given N $=5$ A $=[5,5,1,4,2]$ B $=[5,4,1,5,1]$

We can perform the following operations as:

$1.$ We are currently standing at index $5$ with a cost of A$[5]=2$ We will select the index $2$ and the cost of passing between index $5$ to index $2$ is equal to B$[5]=1$ Then total cost till now is equal to $2-1=3.$

$2.$ In second move we are currently standing at index $2$ with a cost of A$[2]=5$ we can select the index $1$ and the cost of passing between index $2$ and index $1$ is equal to B$[2]5.$ The total cost till now is equal to $35513.$

Hence, total cost is equal to $13.$

Input

Case $2$

Input:

$6$

$5$

$4$

$2$

$4$

$4$

$1$

$1$

$1$

$44334$

Output:

Case $1$

Input:

$55514254151$

Output:

$13$

Explanation:

Given $N=5,A=[5,5,1,4,2],B=[5,4,1,5,1].$

We can perform the following operations as:

Ve are currently standing at index $5$ with a cost of $A[5]=2.$ He wi$11$ select the index $2$ and the cost of passing between index $5$ to index $2$ is equal to $B[S]=1.$ Then total cost till now is equal to $2+1-3.$

In second move we are currently standing at index $2$ with a cost of $A[2]=5,$ we can select the index $1$ and the cost of passing between index $2$ and index $1$ is equal to $B[2]=5.$ The total cost till now is equal to $3+5+5=13.$

Hence, total cost is equal to $13.$