분수 지수

소수

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

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

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

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

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

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

단, $x$는

인 정수로 생각한다.

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

$n\ p\ q$

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

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