题目背景

NFLSPC #6 在即，来不了现场的 SolarPea 要把自己的题目的 std 发给能去现场的 PolarSea。

为了防止有选手窃听他们的通信以获得 std，他们打算使用一个公钥加密算法来确保通信的安全性。

于是 SolarPea 使用了他在知乎上看到的有 “最大的加解密速度和安全性” 的算法，这个算法的安全性 “依赖于大数因子分解难题”：

你是一名拥有 factorization oracle 的参赛选手，并且你已经获得了公钥和明文。请你利用手上的 factorization oracle，破解出 std 吧。

题目描述

由于图片可能看不清，我们重新描述这个加密算法：

• 假设 SolarPea 要给 PolarSea 发一个消息 $M'$，那么他们会进行如下的操作。
• PolarSea 首先生成五个大整数 $P, S_4, S_6, S_7, S_1$，使得 $P < S_6 < S_4P$ 且 $S_5 = S_4P + S_6$ 且 $(S_6\bmod P) ^ 3 < S_4 ^ 3 < S_1 ^ 3 < (S_1 + 1) ^ 3 < S_7 ^ 3 < P$，并计算 $S_3 = S_4P + S_5$。
• 然后 PolarSea 将 $S_3, S_5, S_7, S_1$ 发给 SolarPea。
• SolarPea 拿到了 PolarSea 给他发的四个数。首先，他需要构造一个 $M$ 使得 $S_1 < M < S_7$，并且和 PolarSea 商量好一个通过 $M$ 算出 $M'$ 的方法（例如若 $M'$ 为比较小的正整数，则可以令 $M = M' + S_1$），这个方法是不保密的，所以拿到 $M$ 就相当于拿到 $M'$ 了，所以你可以不用关心 $M'$ 而是只关心 $M$。
• SolarPea 生成了两个满足 $(S_3 - S_5) ^ 3 < r < w$ 的数 $w, r$，并计算 $C = (S_3 - S_5) ^ 3w + MS_5 + r(S_3 - S_5)$，然后将 $C$ 发给 PolarSea。
• PolarSea 只需计算 $\frac{C \operatorname{\bmod} P}{(2S_5 - S_3) \operatorname{\bmod} P}$ 即可获得 $M$。

现在你截获了 PolarSea 和 SolarPea 之间的所有通信（即 $S_3, S_5, S_7, S_1, C$），请你利用已知的信息破解出 $M$。

输入格式

第一行，读入四个整数 $S_3, S_5, S_7, S_1$，表示公钥。

第二行，读入一个整数 $C$，表示密文。

输出格式

输出一行，包含一个值在 $S_1 < M < S_7$ 的整数 $M$，表示破解的明文。可以证明在给定限制下 $M$ 唯一。

7001 4001 7 5
1155511307999246176590006

6

11083610 7305110 52 32
4578384821991465584924042474394616310820101790

39

提示

样例 1 解释

生成的 $P=1000$，$S_4=3$，$S_6=1001$，$S_7=7$，$S_1=5$。计算出的 $S_5=4001$，$S_3=7001$。

密文 $M=6$。加密时选取的 $w=42796713439376$，$r=15045364725522$，加密结果 $C=1155511307999246176590006$。

当然，这次加密是很弱的，因为 $6$ 是 $5$ 和 $7$ 中间的唯一整数。

数据范围与约定

对于所有数据， $P < 10 ^ {500}$，$C < P^{10}$。

• 子任务 1（$20$ 分）：$P < 10 ^ 6$。
• 子任务 2（$20$ 分）：$P < 10 ^ {18}$。
• 子任务 3（$20$ 分）：$P$ 为质数。
• 子任务 4（$20$ 分）：所有数均为随机生成。
• 子任务 5（$20$ 分）：无特殊限制。

Source：NFLSPC #6 E by asmend