为了进入飞船安全系统，星际机械机器人 R2-D2 使用了一种秘密加密算法，其中一步需要解决以下问题：

考虑一条长度为 $n = 2^k$ 的纸带，纸带上的单元格排成一行，编号为 $0$ 到 $n - 1$。将纸带对折，右半部分折叠在左半部分下方，使得编号为 $2^{k-1} - j$ 的单元格位于编号为 $2^{k-1} + j - 1$ 的单元格上方（对于所有 $j$ 从 $1$ 到 $2^{k-1}$）。然后将得到的长度为 $2^{k-1}$ 的纸带以同样的方式反复对折，直到纸带长度为 $1$。在最终折叠好的纸带中，单元格按某种顺序从上到下堆叠。令序列 $a_0, a_1, \dots, a_{n-1}$ 为从上到下单元格的编号。

当机器人连接到飞船系统时，它会得到一个整数 $n$，随后会被要求回答若干查询以进行验证。每个查询是一个区间 $[l, r]$ ($0 \le l \le r < n$)，机器人必须计算以下表达式，其中运算 $+$ 和 $\oplus$ 交替出现：

$$F(l, r) = a_l + a_{l+1} \oplus a_{l+2} + a_{l+3} \oplus a_{l+4} + a_{l+5} \oplus \dots a_r$$

需要特别注意的是，如果 $l$ 是偶数，则运算 $+$ 的优先级高于 $\oplus$；否则，运算 $\oplus$ 的优先级高于 $+$。如果机器人不能在一秒钟内正确回答这些查询，它就会被发现。

R2-D2 与 C-3PO 争论说后者无法解决这个问题。C-3PO 是一个礼仪机器人，它精通六百万种交流方式，但对密码学一窍不通。请帮助它解决这个问题，以便给 R2-D2 一个惊喜。

为了模拟安全系统，R2-D2 建议了一种选择区间 $[l, r]$ 的算法。他还建议只检查 $F(l, r)$ 的哈希结果，而不是 $F(l, r)$ 本身的值。设查询编号为 $0$ 到 $m - 1$，这些值计算如下：

• $h_{j+1} = ((l_j \oplus r_j \oplus h_j \oplus F(l_j, r_j)) + c) \pmod{1\,000\,000\,007}$；
• $l_{j+1} = ((l_j \oplus a \oplus h_{j+1}) \pmod{n + 1}) \pmod n$；
• $r_{j+1} = ((r_j \oplus b \oplus h_{j+1}) \pmod{n - l_{j+1}}) + l_{j+1}$。

其中 $h$ 是哈希函数的值，$h_0 = 0$。你的任务是计算最终的哈希值 $h_m$。

输入格式

第一行包含一个整数 $k$ ($0 \le k \le 30$)。

第二行包含三个整数 $m, l_0, r_0$：查询次数以及初始查询的边界 ($1 \le m \le 10^7, 0 \le l_0 \le r_0 < n$)。

第三行包含三个整数 $a, b, c$：生成算法的参数 ($0 \le a, b, c < 2^{30}$)。

输出格式

输出一个整数 $h_m$：处理完所有查询后的哈希函数值。

样例

样例输入 1

3
1 2 6
3 4 5

样例输出 1

7

样例输入 2

3
709193 4 5
273035200 65685838 991992535

样例输出 2

156951996

说明

运算 $\oplus$ 表示异或。

优先级较高的运算必须先计算。优先级相同的运算必须按照从左到右的顺序处理。

长度为 $2^3 = 8$ 的纸带折叠方式如下图所示：