#59 Fractional Power

Statement

Statement language

Let

M = 998244353

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

yy^{-1} \equiv 1 \pmod M.

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

y^k = \begin{cases} \underbrace{y \cdot y \cdots y}_{k\text{ times}} \pmod M, & k > 0,\\ 1, & k = 0,\\ (y^{-1})^{-k} \pmod M, & k < 0. \end{cases}

If an integer $x$ satisfies

x^q \equiv n^p \pmod M,

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

1 \le x < M.

The input is given in the following format.

$n\ p\ q$

Output the sum of all integers $x$ satisfying

x^q \equiv n^p \pmod {998244353}.

#	Score	Constraints
1	100	Full constraints.

Sample 1

Input

2 3 1

Output

8

Since $q=1$ , we have $x \equiv 2^3 \pmod {998244353}$ . Therefore, the answer is .