[NFLSPC #6] 挑战大数因子分解
题目背景
`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$ 唯一。
输入输出样例
输入样例 #1
7001 4001 7 5
1155511307999246176590006
输出样例 #1
6
输入样例 #2
11083610 7305110 52 32
4578384821991465584924042474394616310820101790
输出样例 #2
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