题目描述

小粉兔喜欢喝冰红茶。

小粉兔的寝室里有$N=2^n-1$桶冰红茶，形如一棵完全二叉树。根节点编号是$1$；对于点$2\le x\le N-1$，$x$的父亲节点是$\lfloor\frac x2\rfloor$。编号为$i$的冰红茶中装着$h_i$ mL 冰红茶。

小粉兔掌管半个寝室的冰红茶。编号为$\frac{N+1}{2}$到$N$的冰红茶是小粉兔室友的；但是对于编号为$1$到$\frac{N-1}{2}$的冰红茶，小粉兔可以任意修改$h_i$。

小粉兔有一套自己的审美观点。他认为寝室里冰红茶的不和谐度为

$$\sum_{x=2}^{N} \left(h_x-h_{\lfloor\frac x2\rfloor}\right)^2$$

小粉兔可以修改$h_1$到$h_{2^{n-1}-1}$。由于是冰红茶，$h_i$可以被修改成任意的非负实数。小粉兔想知道最小的不和谐度是多少。

有时小粉兔的室友会修改一个$h_i$值$(\frac{N+1}{2}\le i\le N)$，这时粉兔需要重新查询最小不和谐度。

由于答案可能是小数，你只需要输出最小不和谐度 $\bmod 1000000007$ 的值。

输入格式

第一行输入两个数$n,q$。$q$是修改的数量。

接下来$\frac{N+1}{2}$个数，代表$h_{\frac{N+1}{2}}, h_{\frac{N+1}{2}+1}, \cdots, h_N$。

接下来$q$行，每行两个数$p, h'$，代表将$h_p$修改为$h'$。保证$\frac{N+1}{2}\le p\le N$。

输入中的$h$均为整数。

输出格式

输出$q+1$行，每行一个数，代表最小不和谐度 $\bmod 1000000007$ 的值。

第一行是修改之前的最小不和谐度；第$i>1$行是第$i-1$次修改之后的最小不和谐度。

样例1

Input

2 0
1 3

Output

2

样例2

Input

3 3
0 1 5 4
6 4
5 4
4 4

Output

333333342
583333342
333333345
0

Hint

最小值分别是$\frac{19}{3},\frac{55}{12},\frac{28}{3},0$。

数据范围

对于所有测试点，$2\le n\le 18, 0\le q\le 500000, 0\le h\le 10^8$。

测试点1-2. $n=2$。

测试点3-5. $q=0$。

测试点6-10. 无特殊限制。