마라톤 코스 설계

문제

마라톤 대회 기획단은 코스를 새로 설계하려 한다. 코스는 n개의 구간으로 이루어지며, 각 구간은 고도가 정확히 1 올라가는 오르막이거나 정확히 1 내려가는 내리막이다. 출발점의 고도는 0이고, 구간을 차례로 지나면서 고도가 바뀐다. 안전 기준에 따라 코스 위의 모든 지점(출발점과 각 구간의 끝 지점)의 고도는 -a 이상이어야 한다. 또한 도착점의 고도는 정확히 h여야 한다. h는 음수일 수도 있다. 오르막과 내리막의 배치가 하나라도 다르면 서로 다른 코스로 센다. 기획단은 조건에 맞는 서로 다른 코스가 몇 가지인지 알고 싶어 하며, 서로 다른 (n, a, h) 조합 T개에 대해 각각 그 수를 구해야 한다. 값이 매우 커질 수 있으므로 각 답을 998,244,353으로 나눈 나머지로 출력한다. 조건을 만족하는 코스가 하나도 없으면 0을 출력한다. 각 질문은 서로 독립이다.

입력

첫 줄에 질문의 수 T가 주어진다. (1 ≤ T ≤ 12,000) 이어서 T개의 줄에 각각 세 정수 n, a, h가 공백으로 구분되어 주어진다. (1 ≤ n ≤ 200,000, 0 ≤ a ≤ 200,000, -200,000 ≤ h ≤ 200,000)

출력

각 질문에 대한 답을 998,244,353으로 나눈 나머지로 한 줄에 하나씩 T줄에 출력한다.

5
4 0 0
3 1 -1
2 5 3
6 2 0
5 0 -1

2
2
0
19
0

2
1 0 1
1 0 -1

1
0

출처: Devin.KR 자체 제작