9999007 - 折纸

月考后的那个晚上，照例是同学们放松嗨皮的时间。Colin 一时想不到有什么好玩的，便找出一张纸折了 起来。这张纸不是普通的 A4 白纸，而是一条长长的纸条，上面打满了黑黑的小点。原来，这是以前物理实 验留下的打点计时器打出的纸带。而且这张纸带不一般，上面有 n = 2k 个均匀分布的点，编号从左到右、从 0 到 n − 1。Colin 开始将这条纸带对折，他把纸带右半边折到了左半边的下面，于是编号为 2 k−1 − j 的点会 在 2 k−1 + j − 1 的上方 (j ∈ [1, 2 k−1 ])。重复折叠 k 次后，纸带变成了 n 层的纸片，记从上到下点的编号为 a0, a1, ..., an−1。Colin 觉得数列 {an} 十分有趣，于是想请你对数列进行一些计算。 定义二元函数 F(l, r) = al + al+1 ⊕ al+2 + al+3 ⊕ al+4 + al+5 ⊕ ...ar，其中当 l 是偶数时 + 的优先级比 ⊕ 高，否则 ⊕ 的优先级比 + 高。 有 m 个询问，给定 l, r，回答 F(l, r)。考虑到 m 非常大，改为求以下递推数列：    hj+1 = ((lj ⊕ rj ⊕ hj ⊕ F(lj , rj )) + c) mod 1 000 000 007 lj+1 = ((lj ⊕ a ⊕ hj+1) mod (n + 1)) mod n rj+1 = ((rj ⊕ b ⊕ hj+1) mod (n − lj+1)) + lj+1 其中 h0 = 0，求 hm。

第一行一个整数 k； 第二行三个整数 m, l0, r0； 第三行三个整数 a, b, c。

输出一行一个整数 hm。