#59 분수 지수

문제

지문 언어

소수

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

인 정수로 생각한다.

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

$n\ p\ q$

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

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

#	점수	제한
1	100	전체 제약을 만족하는 테스트입니다.

예제 1

입력

2 3 1

출력

8

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