Yakov 在 Yandex 排名团队工作，负责搜索引擎的核心部分。

在一次重要发布的前夕，Yakov 注意到其中一条重排规则存在缺陷：它以错误的方式重新排列文档。作为一名尽职尽责的员工，Yakov 不能让这种故障影响用户的搜索体验。

但新的二进制文件已经部署到生产服务器上，距离启用该故障功能的时间所剩无几。因此，Yakov 决定采取孤注一掷的措施：他将尝试通过更改服务器配置文件中的参数来修复所有问题。

Yakov 注意到，在应用新的重排规则后，文档会使用下面给出的 Shuffle 函数进行洗牌。配置文件中 salt 的默认值为零，但 Yakov 正准备更改它。

void Shuffle(int a[N], int salt) {
    for (int i = 0; i < N; ++i) {
        int j = i ^ salt; // bitwise xor with salt
        if (i < j) {
            swap(a[i], a[j]);
        }
    }
}

你可以通过确定此函数的作用来帮助 Yakov。

考虑一个包含 $N$ 个整数的序列 $a_i$。令 Shuffle(a, x) 产生的数组为 $b_x$。

考虑 $x = 0, \dots, N - 1$ 的数组序列 $b_x$。你的任务是找到一个排序排列 $p_i$ ($0 \le p_i < N$)，使得序列 $b_{p_0}, b_{p_1}, \dots, b_{p_{N-1}}$ 有序，即对于 $i = 0, \dots, N - 2$，满足 $b_{p_i}$ 字典序小于或等于 $b_{p_{i+1}}$。此外，对于序列 $p$ 还有一个附加约束：如果对于某些 $p_i$ 和 $p_j$，数组 $b_{p_i}$ 和 $b_{p_j}$ 相等，则必须满足 $p_i < p_j$。

由于考虑的 $N$ 可能很大，你需要输出所求排列的多项式哈希值： $(p_0 \cdot q^{N-1} + p_1 \cdot q^{N-2} + \dots + p_{N-2} \cdot q + p_{N-1}) \pmod{2^{32}}$，其中 $q = 10^9 + 7$。

输入格式

输入包含多个测试用例。每个测试用例包含一行，由九个空格分隔的整数组成：$N, a_{-3}, a_{-2}, a_{-1}, A, B, C, D$ 和 $M$。

所考虑的序列 $a_i$ ($0 \le i < N$) 按以下方式生成： $a_i = (A \cdot a_{i-3} + B \cdot a_{i-2} + C \cdot a_{i-1} + D) \pmod M$。

数据范围： $N = 2^k, 0 \le k \le 17$ $0 \le a_{-3}, a_{-2}, a_{-1}, A, B, C, D \le 10^9$ $1 \le M \le 10^9$ 输入包含的测试用例不超过 $2^{17}$ 个 * 单个输入中所有 $N$ 的总和不超过 $2^{21}$

输出格式

对于每个测试用例，输出一个整数：所求排列的多项式哈希值。

样例

输入 1

4 0 0 1 2 0 3 1 4
4 0 0 1 0 0 1 1 4

输出 1

1628479554
2008884034