题目背景

译自 Izborne Pripreme 2015 (Croatian IOI/CEOI Team Selection) D1T2。$\texttt{1s,0.5G}$。

题目描述

有 $n$ 盏灯泡排成一排，从左到右编号 $1\sim n$。第 $i$ 盏灯泡发光的功率为 $a_i$ 瓦。

现在想要将所有灯泡全部关闭。考虑如下的贪心算法：

• 选择起始位置 $p$。关闭灯泡 $p$。
• 令当前位置为 $x$。若还有灯泡未关闭，循环执行以下流程：
  • 若只有 $x$ 左边有未关闭的灯泡，则关闭 $x$ 左边离 $x$ 最近的灯泡 $l$，并令 $x\gets l$。
  • 若只有 $x$ 右边有未关闭的灯泡，则关闭 $x$ 右边离 $x$ 最近的灯泡 $r$，并令 $x\gets r$。
  • 否则，$x$ 左边离 $x$ 最近的灯泡为 $l$，令 $x$ 右边离 $x$ 最近的灯泡为 $r$。
    • 如果两盏灯泡功率相等，则随机选择一盏灯泡 $y$。关闭 $y$，并令 $x\gets y$。
    • 否则，令功率更大的灯泡为 $y$。关闭 $y$，并令 $x\gets y$。

定义 $f(p)$ 为起始位置为 $p$ 时，上述贪心算法产生的不同关灯泡序列有多少个。

给定 $m$ 个位置 $x_1,x_2,\cdots,x_m$。对于 $i=1,2,\cdots,m$，求出 $f(x_i)$ 对 $(10^9+7)$ 取模后的结果。

输入格式

第一行，两个正整数 $n,m$。

第二行，$n$ 个正整数 $a_1,a_2,\cdots,a_n$。

第三行，$m$ 个正整数 $x_1,x_2,\cdots,x_m$。

输出格式

输出 $m$ 行。每行一个整数，表示答案对 $(10^9+7)$ 取模后的结果。

5 2
3 5 1 4 3
3 5

2
1

7 7
7 7 7 7 7 7 7
7 6 5 4 3 2 1

1
6
15
20
15
6
1

提示

样例解释

样例 $1$ 解释：起始位置为 $3$ 时，$[3,2,4,1,5]$ 和 $[3,2,4,5,1]$ 是可能的两种关灯泡顺序。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le x_i\le n\le 2\times 10^5$；
• $1\le a_i,m\le 2\times 10^5$。