Byteland 军队中有 $$$n$$$ 军官。每个军官都有一些与他相关的权力。第 $$$i$$$ 军官的权力由 $$$p_{i}$$$ 表示。战争临近,将军想知道军队的实力。
在拜特兰,军队的兵力计算方式很奇怪。将军从这些 $$$n$$$ 军官中随机选择一个军官子集,并将该子集称为营。($$$n$$$ 军官的所有 $$$2^n$$$ 子集可以同等概率地选择,包括空子集和所有军官的子集)。
营的兵力按以下方式计算:
设所选官员的权力为 $$$a_{1},a_{2},\ldots,a_{k}$$$,其中 $$$a_1 \le a_2 \le \dots \le a_k$$$。该营的兵力等于$$$a_1a_2 + a_2a_3 + \dots + a_{k-1}a_k$$$。 (如果营的规模为$$$\leq 1$$$,则该营的兵力为$$$0$$$)。
军队兵力等于营兵力预期值。
由于战争确实很漫长,军官的权力可能会发生变化。准确地说,将会有 $$$q$$$ 的变化。 $$$i$$$ $$$x$$$ 形式中的每一个表示 $$$p_{i}$$$ 更改为 $$$x$$$。
你需要在最初和每次 $$$q$$$ 更新之后找到军队的实力。
请注意,这些更改是永久性的。
强度应通过模 $$$10^{9}+7$$$ 求出。正式地,令 $$$M=10^{9}+7$$$。可以证明,答案可以表示为不可约分数 $$$p/q$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q\not\equiv 0 \bmod M$$$)。输出等于 $$$p\cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出这样一个整数 $$$x$$$ 使得 $$$0 \leq x < M$$$ 且 $$$x ⋅ q \equiv p \bmod M$$$)。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3⋅10^{5}$$$) — Byteland 军队的军官人数。
第二行包含 $$$n$$$ 整数 $$$p_{1},p_{2},\ldots,p_{n}$$$ ($$$1 \leq p_{i} \leq 10^{9}$$$)。
第三行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 3⋅10^{5}$$$) — 更新次数。
接下来的 $$$q$$$ 行包含两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \leq i \leq n$$$, $$$ 1 \leq x \leq 10^{9}$$$),表示 $$$p_{i}$$$ 更新为 $$$x$$$ 。
输出
第一行输出军队初始兵力。
在接下来的$$$q$$$行中,输出第$$$i$$$更新后的军队实力。
示例
输入 #1
2 1 2 2 1 2 2 1
输出 #1
500000004 1 500000004
输入 #2
4 1 2 3 4 4 1 5 2 5 3 5 4 5
输出 #2
625000011 13 62500020 375000027 62500027
注意
在第一个测试用例中,最初有四个可能的营
- {} 强度 = $$$0$$$
- {$$$1$$$} 强度 = $$$0$$$
- {$$$2$$$} 强度 = $$$0$$$
- {$$$1,2$$$} 强度 = $$$2$$$
将$$$p_{1}$$$更改为$$$2$$$后,营兵力{$$$1,2$$$}更改为$$$4$$$,因此陆军兵力变为$$$1$$$。
将$$$p_{2}$$$更改为$$$1$$$后,营的兵力{$$$1,2$$$}再次变为$$$2$$$,因此军队的兵力变为$$$\frac{1}{2}$$$。