#59 Fractional Power

Loading problem...

Preparing the statement, recent submissions, and submit form.

#59 Fractional Power | DOJ

Authors: Admin

Statement

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

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

Sample 2

Input

2 1 -1

Output

499122177

The value satisfying $x^{-1} \equiv 2 \pmod {998244353}$ is the modular inverse of $2$ , which is $499122177$ .

Sample 3

Input

2 1 3

Output

275347185

We have $275347185^3 \equiv 2 \pmod {998244353}$ .