'('와 ')' 괄호로만 이루어진 문자열을 고려하자. 올바른 괄호 문자열(regular bracket sequence)은 다음 규칙에 따라 얻을 수 있는 문자열이다:

• 빈 문자열은 올바른 괄호 문자열이다.
• $A$가 올바른 괄호 문자열이면, $(A)$도 올바른 괄호 문자열이다.
• $A$와 $B$가 올바른 괄호 문자열이면, $A$와 $B$를 이어 붙인 것도 올바른 괄호 문자열이다.

$1, 2, \dots, N$으로 번호가 매겨진 $N$개의 상자와 두 정수 $M$과 $K$가 주어진다. 각 상자에 정확히 하나의 올바른 괄호 문자열을 넣어 다음 조건을 만족하도록 하는 것이 목표이다:

• $N$개의 상자에 들어 있는 모든 '(' 괄호의 총개수는 $M$과 같다.
• 길이가 $2 \cdot K$인 올바른 괄호 문자열은 상자에 넣을 수 없다.

이러한 방법의 수를 구하시오. 두 분포는 어떤 상자 $i$에 대해 그 상자에 들어 있는 올바른 괄호 문자열이 서로 다를 경우 서로 다른 것으로 간주한다. 정답이 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 출력하시오.

입력

입력은 세 정수 $N, M, K$를 포함하는 한 줄로 구성된다 ($1 \le M, N \le 10^6$, $1 \le K \le M$).

출력

$998\,244\,353$으로 나눈 나머지를 출력하시오.

예제

입력 1

2 2 1

출력 1

4

입력 2

1 1 1

출력 2

0

입력 3

24 120 30

출력 3

379268651

참고

첫 번째 예제에서, 다음 분포들이 조건을 만족한다:

• $(())$, empty;
• $()()$, empty;
• empty, $(())$;
• empty, $()()$.

따라서 정답은 4이다.