你发现了一个奇怪的谜题，它看起来像一棵高度为 $N$ 的满二叉树（从根节点到任意叶子节点的路径上有 $N$ 个节点）。树中节点的编号方式如下：根节点的编号为 1，任何非叶子节点 $x$ 都有两个子节点，编号分别为 $2x$（我们称之为左子节点）和 $2x + 1$（右子节点）。

每个节点都有自己的状态，可以是 0 或 1。你可以通过从任意节点开始一次翻转反应（flipping reaction）来改变状态。翻转反应的过程如下：首先，被翻转节点的状态变为其相反状态。之后，如果该节点不是叶子节点，连锁反应将继续在其一个子节点上进行：如果该节点在翻转前的状态为 0，则翻转反应在其左子节点上继续；否则，在其右子节点上继续。因此，翻转反应会沿着从起始节点到恰好一个叶子节点的路径进行。

在从某个节点开始一次翻转反应后，你必须等待整个反应结束，然后才能开始下一次反应。每个节点都可以作为翻转反应的起始节点任意次。

给你所有节点的初始状态。你的目标是通过启动最少次数的翻转反应，将所有状态都设置为 0。

由于节点数量可能非常大，我们无法在输入文件中直接给出所有状态。幸运的是，你可以使用以下算法获取所有状态：在输入文件中，你将获得整数 $a, b, c, p$ 和 $T$，其中 $p$ 是质数，$b$ 是正数。使用这些数字，你可以生成序列 $x_i$：

$$x_1 = a$$ $$x_i = (x_{i-1} \cdot b + c) \bmod p \quad \text{其中 } i > 1$$

对于每个节点 $i$，如果 $x_i \ge T$，则第 $i$ 个节点的初始状态为 1，否则为 0。

输入格式

输入的唯一一行包含六个整数 $N, a, b, c, p$ 和 $T$（$1 \le N \le 60, 0 \le a < p, 1 \le b < p, 0 \le c < p, 2 \le p \le 1\,000\,000, 0 < T < p$）。保证 $p$ 是质数。

输出格式

输出将所有节点的状态设置为 0 所需的最少翻转反应次数。

样例

输入样例 1

3 3 2 1 5 2

输出样例 1

4

输入样例 2

4 4 1 0 7 3

输出样例 2

8