#59 Fractional Power

Loading problem...

Preparing the statement, recent submissions, and submit form.

#59 Fractional Power | DOJ

Authors: Admin

Time limit: 1000 ms
Python time limit: 2000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

소수

M = 998244353

에 대하여 세 정수 $n,p,q$ 가 주어진다.

먼저 음수 지수를 다음과 같이 정의한다. $y \not\equiv 0 \pmod M$ 일 때, $y^{-1}$ 은

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

을 만족하는 유일한 정수이다.

정수 $k$ 에 대하여 $y^k \pmod M$ 는 다음과 같이 정의한다.

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

정수 $x$ 가 다음 합동식을 만족하면, $x$ 를 $n^{p/q} \pmod M$ 의 가능한 값이라고 하자.

x^q \equiv n^p \pmod M

주어진 $n,p,q$ 에 대하여 가능한 모든 정수 $x$ 의 합을 출력하여라.

단, $x$ 는

1 \le x < M

인 정수로 생각한다.

Input

입력은 다음과 같은 형식으로 주어진다.

$n\ p\ q$

Output

다음 합동식을 만족하는 모든 정수 $x$ 의 합을 출력한다.

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

Constraints

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

Subtasks

#	Score	Constraints
1	100	전체 제약을 만족하는 테스트입니다.

Samples

Sample 1

Input

2 3 1

Output

$q=1$ 이므로 $x \equiv 2^3 \pmod {998244353}$ 이다. 따라서 답은 $8$ 이다.

Sample 2

Input

2 1 -1

Output

499122177

$x^{-1} \equiv 2 \pmod {998244353}$ 을 만족하는 $x$ 는 $2$ 의 역원인 $499122177$ 이다.

Sample 3

Input

2 1 3

Output

275347185

$275347185^3 \equiv 2 \pmod {998244353}$ 이다.

Editorial

View editorial

분수 지수

Statement

Input

Output

Constraints

Subtasks

Samples

Editorial