Turning off the bulbs

Every morning, when the first sunlight appears, Ivan has to turn off all the light bulbs in the street lights of his village. The village has a single straight road, and the street lights stand on one side of it, numbered 1 to $N$ from left to right.

Each day Ivan picks a starting street light $p$ and turns off its bulb first. After that he saves electricity by following one rule. At every step he looks at the nearest bulb that is still on to the left and the nearest bulb that is still on to the right, and turns off the one with the bigger power. If no bulb is on to the left, he turns off the nearest bulb on the right, and if no bulb is on to the right, he turns off the nearest bulb on the left. If the two bulbs have equal power, Ivan can turn off either one of them. That is why the same starting position can produce several different orders of turning the bulbs off.

Let $M(p)$ be the number of different orders when Ivan starts at $p$. For the $K$ given starting positions, compute $M(P_i)$ modulo $10^9 + 7$.

The first line contains the number of street lights $N$ and the number of starting positions $K$, separated by a space.

The second line contains the powers of the bulbs $A_1, A_2, \dots, A_N$, separated by spaces.

The third line contains the starting positions $P_1, P_2, \dots, P_K$, separated by spaces. The same position can appear more than once.

Print $K$ lines. The $i$-th line contains $M(P_i)$ modulo $10^9 + 7$.

• $1 \le N \le 100\,000$
• $1 \le K \le 100\,000$
• $1 \le A_i \le 200\,000$
• $1 \le P_i \le N$

Consider five street lights with powers $3, 5, 1, 4, 3$. If Ivan starts at street light 3, he turns off bulb 3 and reaches $(3, 5, \times, 4, 3)$. The left bulb has the bigger power, so he turns off bulb 2 and reaches $(3, \times, \times, 4, 3)$. Now the right bulb has the bigger power, so he turns off bulb 4 and reaches $(3, \times, \times, \times, 3)$. Bulbs 1 and 5 have equal power, so either one can go first and the order splits into two.

Starting at street light 5 in the same village, no bulb is ever on to the right, so the only order turns the bulbs off from right to left.