관람차

거대 관람차 Cosmo Clock 21은 요코하마의 랜드마크이며 도시의 야경을 아름답게 만든다. ICPC 도시도 이와 비슷한 관람차를 세우고 싶어 한다.

ICPC 도시는 곤돌라 수가 짝수인 조명 관람차를 지을 계획이다. 모든 곤돌라는 주어진 후보 색 중 하나로 칠한다. 조명 계획은 다음과 같다.

• 모든 곤돌라를 두 개씩 짝짓고, 각 곤돌라는 정확히 한 쌍에 속한다.
• 같은 색인 곤돌라 두 개만 한 쌍이 될 수 있다.
• 짝을 이룬 곤돌라는 직선 LED 선으로 연결하여 관람차를 밝힌다.
• 앞면에서 볼 때 두 LED 선이 교차하지 않는다.

곤돌라의 색칠이 적합하다는 것은 이 조명 계획에 맞는 짝짓기가 적어도 하나 있다는 뜻이다.

그림 C.1. 적합한 색칠(왼쪽)과 적합하지 않은 색칠(오른쪽)의 관람차

곤돌라 수와 후보 색의 수가 주어질 때, 적합한 곤돌라 색칠의 수를 구하라. 관람차는 회전하므로, 어떤 회전으로 일치하는 두 색칠은 같은 것으로 본다. 반대편에서 볼 때만 일치하는 두 색칠은 서로 다른 것으로 본다.

입력은 다음 형식의 테스트 케이스 하나로 주어진다.

$n$ $k$

$n$과 $k$는 $1$ 이상 $3 \times 10^6$ 이하의 정수이다. 곤돌라 수는 $2n$이고, 후보 색의 수는 $k$이다.

적합한 곤돌라 색칠의 수를 $998\\, 244\\, 353 = 2^{23} \\times 7 \\times 17 + 1$로 나눈 나머지를 출력한다. 이 수는 소수이다.

$n = 3$, $k = 2$인 경우 아래 그림과 같이 적합한 색칠은 여섯 가지이다.

그림 C.2. $n = 3$, $k = 2$인 경우의 적합한 색칠