Arithmetic and Geometric Sequences

The arithmetic sequence $A$ has general term $a + b \times x$ and the geometric sequence $G$ has general term $c \times d^y$, where $x$ and $y$ are non-negative integers.

Given $a$, $b$, $c$, $d$, and $u$, write a program that counts the integers from $1$ to $u$ that belong to $A$ or to $G$. A number that belongs to both sequences is counted as well. If the same number appears several times in a sequence, it still counts once.

The first line contains $a$, $b$, $c$, $d$, and $u$, separated by spaces. ($1 \le a, b, c, u \le 10^{12}$, $1 \le d \le 10^5$)

Print on the first line how many integers between $1$ and $u$ inclusive belong to the arithmetic sequence $A$ or to the geometric sequence $G$.

For $a = 452$, $b = 24$, $c = 4$, $d = 5$, and $u = 600$, the numbers that satisfy the condition are $4$, $20$, $100$, $452$, $476$, $500$, $524$, $548$, $572$, $596$.