Fractional Power

Let

be a prime number. You are given three integers $n,p,q$.

First, define negative exponents as follows. When $y \not\equiv 0 \pmod M$, $y^{-1}$ is the unique integer satisfying

For an integer $k$, define $y^k \pmod M$ as follows.

If an integer $x$ satisfies

then $x$ is called a possible value of $n^{p/q} \pmod M$.

Given $n,p,q$, output the sum of all possible integers $x$.

Here, $x$ is considered as an integer satisfying

The input is given in the following format.

$n\ p\ q$

Output the sum of all integers $x$ satisfying

• $1 \le n < 998244353$.
• $-10^{18} \le p,q \le 10^{18}$.
• $\gcd(|q|,998244352)=1$.