Problem Description

In the Kingdom of E869120, there are $N$ towns, and town $i-1$ and town $i$ are connected by a road.

Additionally, each town $i$ $(1 \leq i \leq N)$ has an integer $a_i$ written on it, and the length of the road is determined according to the following rule:

• The length of the road connecting town $i-1$ and town $i$ is $a_{i-1} \times a_i$.

Square1001, who lives in the Kingdom of E869120, has decided to go for a walk.

Square1001 lives in town $1$ and is supposed to walk the route $1 \rightarrow c_1 \rightarrow c_2 \rightarrow ... \rightarrow c_Q \rightarrow 1$.

However, Square1001 might walk an incredible distance, so you are asked to tell Square1001 the distance they will walk.

Calculate the distance Square1001 will walk modulo $1,000,000,007$.

Input Format

The input is given in the following format:

$N$ $Q$ $a_1$ $a_2$ $...$ $a_N$ $c_1$ $c_2$ $...$ $c_Q$

• The first line contains the number of towns $N$ and the number of waypoints $Q$, separated by spaces.
• The second line contains the integers $a_1, a_2, ... a_N$ written on the towns, separated by spaces.
• The third line contains the integers $c_1, c_2, ... c_Q$ representing the walking route of Square1001, separated by spaces.

Output Format

Follow the following format for the output:

The first line should contain the distance Square1001 will walk modulo $1,000,000,007$. Ensure there is a newline at the end of the output.

Sample Input and Output

Sample Input #1

4 3
5 3 1 2
3 2 4

Sample Output #1

264

Sample Input #2

3 2
23 12 9
2 3

Sample Output #2

876796540

Sample Input #3

2 1
1000000000 1000000000
2

Sample Output #3

625113690

Notes/Hints

Constraints

• $2 \leq N \leq 120,000$
• $1 \leq Q \leq 120,000$
• $0 \leq a_i \leq 1,000,000,000$
• $1 \leq c_i \leq N$
• $c_{i-1} \neq c_i$
• $a_i = 0 \Rightarrow a_{i+1} \neq 0$

Partial Points

• If you correctly answer test cases satisfying $1 \leq N \leq 1,000$ and $1 \leq Q \leq 1,000$ and $1 \leq a_i \leq 1,000$, you will be awarded 15 points as partial credit.
• If you correctly answer test cases satisfying $1 \leq N \leq 1,000$ and $1 \leq Q \leq 1,000$, you will be awarded 50 points as partial credit.
• If you correctly answer all test cases, you will be awarded 100 points.

Sample Explanation 1

• The first time, walking from town $1$ to town $3$, Square1001 walks $5^3 + 3^1 = 128$ steps.
• The second time, walking from town $3$ to town $2$, Square1001 walks $3^1 = 3$ steps.
• The third time, walking from town $2$ to town $4$, Square1001 walks $3^1 + 1^2 = 4$ steps.
• The fourth time, walking from town $4$ to town $1$, Square1001 walks $1^2 + 3^1 + 5^3 = 129$ steps.
• Therefore, Square1001 walks a total of $264$ steps.

Sample Explanation 2

Square1001 walks $43,829,259,183,601,346$ steps, so the output is the remainder when divided by $1,000,000,007$, which is $876,796,540$.

Sample Explanation 3

How much should Square1001 walk?

见题面 Input 部分

见题面 Output 部分