$1$부터 $N$까지의 정수로 각각 라벨이 붙은 상자가 하나씩 있다. 또한, $1$부터 $N$까지의 각 정수에 대해 해당 정수로 라벨이 붙은 공이 $M$개씩 있다.
이 $NM$개의 공을 섞은 뒤 $N$개의 상자에 분배하는데, 각 상자에는 정확히 $M$개의 공이 들어간다.
공을 배치하는 방법은 총 $\frac{(NM)!}{(M!)^N}$가지가 있으며(모든 공을 구별 가능한 것으로 간주할 경우), 이 모든 배치는 동일한 확률로 발생한다.
당신은 이 상자와 공들에 대해 일련의 작업을 수행한다. 한 번의 작업은 다음 단계들로 구성된다.
- 상자 하나를 선택하여 그 상자 앞에 선다.
- 그 상자에 공이 없으면 작업을 종료한다.
- 그 상자에서 공 하나를 선택하여 상자 밖으로 버린다.
- 마지막으로, 방금 버린 공의 라벨과 일치하는 라벨이 붙은 상자 앞으로 이동한 뒤, 2단계로 돌아간다.
모든 $NM$개의 공이 버려질 때까지 필요한 작업 횟수를 점수라고 정의한다. 당신은 이 점수를 최소화하고자 한다.
최적으로 행동했을 때 점수의 기댓값을 $998244353$으로 나눈 나머지를 구하라.
입력
첫 번째 줄에는 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 10^5$, $1 \le M \le 100$)
출력
정답을 출력한다.
예제
입력 1
2 2
출력 1
166374060
입력 2
3 1
출력 2
831870296
입력 3
100000 100
출력 3
402978825
참고
첫 번째 예제에 대해, 가능한 공의 배치와 그에 따른 최적의 작업 방식은 다음과 같다.
상자 1에 라벨 1인 공 2개를 넣고, 상자 2에 라벨 2인 공 2개를 넣는 경우 (확률 $1/6$)
- 첫 번째 작업에서 상자 1 앞에 선다. 거기서 라벨 1인 공을 꺼내고 상자 1 앞에 선다. 그 다음 라벨 1인 공을 하나 더 꺼내고 다시 상자 1 앞에 선다. 이 시점에서 상자 1이 비어 있으므로 작업을 종료한다.
- 두 번째 작업에서 상자 2 앞에 선다. 거기서 라벨 2인 공을 꺼내고 상자 2 앞에 선다. 그 다음 라벨 2인 공을 하나 더 꺼내고 다시 상자 2 앞에 선다. 이 시점에서 상자 2이 비어 있으므로 작업을 종료한다.
- 이 경우, 최소 달성 가능한 점수는 2이다.
상자 1과 상자 2 각각에 라벨 1인 공 1개와 라벨 2인 공 1개를 넣는 경우 (확률 $2/3$)
- 첫 번째 작업에서 상자 1 앞에 선다. 거기서 라벨 1인 공을 꺼내고 상자 1 앞에 선다. 그 다음 라벨 2인 공을 꺼내고 상자 2 앞에 선다. 그 다음 라벨 2인 공을 꺼내고 상자 2 앞에 선다. 그 다음 라벨 1인 공을 꺼내고 상자 1 앞에 선다. 이 시점에서 상자 1이 비어 있으므로 작업을 종료한다.
- 이 경우, 최소 달성 가능한 점수는 1이다.
상자 1에 라벨 2인 공 2개를 넣고, 상자 2에 라벨 1인 공 2개를 넣는 경우 (확률 $1/6$)
- 첫 번째 작업에서 상자 1 앞에 선다. 거기서 라벨 2인 공을 꺼내고 상자 2 앞에 선다. 그 다음 라벨 1인 공을 꺼내고 상자 1 앞에 선다. 그 다음 라벨 2인 공을 꺼내고 상자 2 앞에 선다. 그 다음 라벨 1인 공을 꺼내고 상자 1 앞에 선다. 이 시점에서 상자 1이 비어 있으므로 작업을 종료한다.
- 이 경우, 최소 달성 가능한 점수는 1이다.
요약하자면, 최소 점수는 확률 $1/6$로 2점, 확률 $5/6$로 1점이 되며, 전체 기댓값은 $7/6$이다. 따라서 $166374060$을 출력한다. 이는 이 값을 $998244353$으로 나눈 나머지이다.
기댓값 모듈로 998244353 정의
구해야 할 기댓값은 항상 유리수임이 증명될 수 있다. 또한, 이 문제의 제약 조건 하에서 기댓값이 기약 분수 $\frac{y}{x}$로 표현될 때, $x$는 $998244353$으로 나누어떨어지지 않음이 보장된다.
이 경우, $xz \equiv y \pmod{998244353}$을 만족하는 $0$ 이상 $998244352$ 이하의 유일한 정수 $z$가 존재한다. 이 $z$를 출력하라.