时空限制

1S/512M

题目描述

给定两个初始整数 $A$ 和 $D$，以及三个参数 $B, C, P$。

你可以对整数 $A$ 和 $D$ 执行以下两种操作：

1. 加法操作: 将数字 $x$ 变为 $(x + B) \bmod P$。
2. 乘法操作: 将数字 $x$ 变为 $(x \times C) \bmod P$。

这些操作的代价计算方式如下，对 $A$ 和 $D$ 的操作次数独立计算：

• 对 $A$ 进行的第 $i$ 次操作（无论是加法或乘法），代价为 $2^{i - 1}$。
• 对 $D$ 进行的第 $j$ 次操作（无论是加法或乘法），代价为 $2^{j - 1}$。

你的目标是，通过对 $A$ 和 $D$ 各进行若干次操作，使得它们的值相等。你需要求出达成该目标所需的最小总代价。总代价为对 $A$ 操作的总代价与对 $D$ 操作的总代价的和。

由于代价可能很大，你需要将总代价对 $998244353$ 取模。如果无法通过上述操作使 $A$ 和 $D$ 相等，输出 -1。

格式

输入格式

输入一行，包含五个整数 $A, D, B, C, P$。

输出格式

输出一个整数。如果经过操作后 $A$ 和 $D$ 可以相等，输出最小的总代价，答案对 $998244353$ 取模。如果它们永远无法相等，输出 -1。

样例

样例输入 #1

6 10 1 3 13

样例输出 #1

4

样例解释 #1

• 对 $A$ 的操作:
  1. $6 \to (6 \times 3) \bmod{13} = 5$。

这是对 $A$ 的第 1 次操作，代价为 $2^{0} = 1$。

• 对 D 的操作:
  1. $10 \to (10 \times 3) \bmod{13} = 4$。
  2. $4 \to (4 + 1) \bmod{13} = 5$。

这是对 $D$ 的第 $1$ 次和第 $2$ 次操作，总代价为 $2^{0} + 2^{1} = 1 + 2 = 3$。

最小总代价为 $1 + 3 = 4$。

数据规模

对于 $30\%$ 的数据，$P < 2000$。

对于 $100\%$ 的数据，$0 \le A, D, B, C < P$，$2 \le P \le 10^6$。