Fermat's Last Theorem

Fermat's Last Theorem states the following.

$\nexists (x, y, z) \in (\mathbb{Z}\setminus\{0\})^3 \quad \text{s.t.} \quad x^n + y^n = z^n \ (n \ge 3, n \in \mathbb{Z}, xyz \ne 0)$

Source: Facebook math gallery

Changho, who dreams of studying abroad, believes in Western learning, as the picture above shows. He boasts that he went beyond Fermat's Last Theorem and built his own, 'Changho's Last Theorem'. First, for an integer $k \ge 2$, call the set of distinct primes that appear in the prime factorization of $k$ the prime set of $k$, written $\mathbb{p}(k)$. Since $1$ cannot be factored into primes, $\mathbb{p}(1) = \emptyset$. That is, if $k = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ where the $p_i$ are distinct primes and each $e_i \ge 1$ is an integer, then $\mathbb{p}(k) = \{p_1, p_2, \cdots, p_t\}$. Changho's Last Theorem is as follows.

For an odd nonnegative integer $n$ and nonzero integers $x$ and $y$ with $x + y \ne 0$, if there exists an integer $z \ge 1$ such that $\mathbb{p}(z) \cap \mathbb{p}(\lvert x\rvert) = \emptyset$, $\mathbb{p}(z) \cap \mathbb{p}(\lvert y\rvert) = \emptyset$, and $\mathbb{p}(z) \subseteq \mathbb{p}(\lvert x+y\rvert)$, then for every nonnegative integer $m$, $\lvert x^n + y^n\rvert$ cannot be a multiple of $z^m$.

Dongwoo found that this claim has many counterexamples. Given $n$, $x$, $y$, and $m$, count the $z^m$ that break the claim and sum them. That is, find the number and the sum of all $z^m$ that satisfy $\mathbb{p}(z) \cap \mathbb{p}(\lvert x\rvert) = \emptyset$, $\mathbb{p}(z) \cap \mathbb{p}(\lvert y\rvert) = \emptyset$, and $\mathbb{p}(z) \subseteq \mathbb{p}(\lvert x+y\rvert)$, where $\lvert x^n + y^n\rvert$ is a multiple of $z^m$.

The first line contains an odd nonnegative integer $n$ ($1 \le n \le 10^{18}$, $n \equiv 1 \pmod{2}$), nonzero integers $x$ and $y$ ($1 \le \lvert x\rvert, \lvert y\rvert \le 10^{18}$, $x + y \ne 0$), and an integer $m$ ($1 \le m \le 10^{18}$), separated by spaces.

For the given $n$, $x$, $y$, and $m$, print the number and the sum of all $z^m$ that satisfy $\mathbb{p}(z) \cap \mathbb{p}(\lvert x\rvert) = \emptyset$, $\mathbb{p}(z) \cap \mathbb{p}(\lvert y\rvert) = \emptyset$, $\mathbb{p}(z) \subseteq \mathbb{p}(\lvert x+y\rvert)$, and for which $\lvert x^n + y^n\rvert$ is a multiple of $z^m$, each taken modulo $1\,000\,000\,007$. Separate the two values with a space.