또 다른 동전 무게 재기 퍼즐

여러 봉지에 동전이 들어 있다. 각 봉지에는 정확히 $k$개의 동전이 들어 있다. 정확히 한 봉지만 가짜 동전으로만 채워져 있고(이 봉지를 가짜 봉지라고 부르자), 나머지 봉지는 모두 진짜 동전으로만 채워져 있다. 모든 진짜 동전의 무게는 정확히 같다. 모든 가짜 동전의 무게도 정확히 같다. 진짜 동전과 가짜 동전의 정확한 무게는 알지 못한다. 가짜 동전이 진짜 동전보다 무겁다는 것만 알고, 얼마나 더 무거운지는 모른다. 동전의 무게는 양의 실수이다.

최대 $m$번 사용할 수 있는 저울이 있다. 저울에는 왼쪽 접시와 오른쪽 접시가 있다. 저울을 사용하려면, 어느 봉지에서든 원하는 만큼 동전을 꺼내 왼쪽과 오른쪽 접시에 올릴 수 있다. 단, 왼쪽과 오른쪽 접시에 올린 동전의 총 개수는 정확히 같아야 한다. 저울은 하나의 실수 $s$를 반환한다. $s$가 0이면 양쪽 접시의 무게가 정확히 같다. $s$가 음수이면 왼쪽 접시가 오른쪽 접시보다 $|s|$그램 더 무겁다. $s$가 양수이면 오른쪽 접시가 왼쪽 접시보다 $s$그램 더 무겁다. 동전은 서로 다른 무게 재기에 여러 번 사용할 수 있고, 각 동전이 어느 봉지에서 나왔는지 추적할 수 있다. 수행할 모든 무게 재기를 미리 정해야 한다(따라서 이전 재기의 결과를 보고 다음 재기에서 무엇을 올릴지 조정할 수 없다). 저울을 $m$번 사용한 뒤 어느 봉지가 가짜 봉지인지 알아내려고 한다.

이제 궁금한 것은, $m$과 $k$가 주어졌을 때 항상 가짜 봉지를 알아낼 수 있는 최대 봉지 수이다. 이 수는 매우 커질 수 있으므로 큰 소수 998,244,353으로 나눈 나머지를 출력한다.

입력은 한 줄이며, 공백으로 구분된 두 정수 $m$과 $k$가 주어진다($1 \le m, k \le 10^6$). $m$은 사용할 수 있는 무게 재기의 횟수이고 $k$는 각 봉지에 들어 있는 동전의 개수이다.

$m$번의 무게 재기로 가짜 봉지를 알아낼 수 있는 최대 봉지 수를 큰 소수 998,244,353으로 나눈 나머지를 한 줄에 출력한다.

동전이 1개씩 들어 있는 9개의 봉지 중에서 가짜 봉지를 2번의 무게 재기로 알아내는 방법 중 하나는 다음과 같다.

• 첫 번째 재기에서 1, 2, 3번 봉지의 동전을 왼쪽에, 7, 8, 9번 봉지의 동전을 오른쪽에 올린다.
• 두 번째 재기에서 1, 4, 7번 봉지의 동전을 왼쪽에, 3, 6, 9번 봉지의 동전을 오른쪽에 올린다.

가짜 봉지는 다음과 같이 알아낼 수 있다.

• 첫 번째 재기로 어느 봉지 묶음 (1, 2, 3), (4, 5, 6), (7, 8, 9)에 가짜 봉지가 있는지 알 수 있다(예를 들어 왼쪽이 더 무거우면 (1, 2, 3)에, 양쪽이 같으면 (4, 5, 6)에, 그렇지 않으면 (7, 8, 9)에 가짜 봉지가 있다).
• 두 번째 재기로 어느 봉지 묶음 (1, 4, 7), (2, 5, 8), (3, 6, 9)에 가짜 봉지가 있는지 알 수 있다. 두 결과를 종합하면 가짜 봉지를 하나로 특정할 수 있다.