훈련, 3라운드

Ashley는 Brandon's Online Judge에서 다음 프로그래밍 대회를 준비하고 있다.

Ashley에게는 다음 대회까지 $k$주가 남아 있다. 코치 Tom은 매우 바빠서 더 이상 Ashley가 풀 문제를 직접 고르지 않는다. 매주 초에 Tom은 Brandon's Online Judge의 문제 은행에 있는 $n$개 문제 중에서 서로 다른 $p$개의 문제를 고른다. 각 주의 선택은 서로 독립적이며 모든 경우가 같은 확률로 일어난다. Tom은 이 방식으로 총 $k$개의 문제 묶음을 만든다.

Ashley는 Tom이 고른 문제를 모두 푼다. 그러나 서로 다른 두 주에 공통된 문제가 하나라도 있으면 짜증이 난다. 그녀는 중복되지 않는 새로운 문제만 풀고 싶어 하기 때문이다.

Ashley가 짜증을 내게 될 확률을 구하라.

입력은 한 줄이며, 세 정수 $n$ $(1 \le n \le 10^7)$, $k$ $(1 \le k \le 10^7)$, $p$ $(1 \le p \le n)$가 주어진다.

Ashley가 짜증을 내게 될 확률을 $p$라 하자. 이 확률 $p$는 기약분수 $\frac{x}{y}$로 나타낼 수 있으며, $\gcd(x, y) = 1$이고 $y \not\equiv 0 \pmod{998244353}$이다. $[0, 998244353)$ 범위의 정수 중 $r \cdot y \equiv x \pmod{998244353}$를 만족하는 유일한 정수를 $r$이라 하자. $r$을 출력하라.

주어진 제약 조건에서 $r$이 존재하고 유일함은 보장된다.

첫 번째 샘플에서 Ashley가 짜증을 내게 될 확률은 $\frac{7}{9}$이다. $110916040 \cdot 9 \equiv 7 \pmod {998244353}$이므로 출력은 110916040이다.

두 번째 샘플에서는 Ashley가 항상 짜증을 낸다. $1 \cdot 1 \equiv 1 \pmod {998244353}$이므로 출력은 1이다.

세 번째 샘플에서는 Ashley가 짜증을 내지 않는다. $0 \cdot 1 \equiv 0 \pmod {998244353}$이므로 출력은 0이다.