시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB64262142.000%

문제

두 정수 $N$, $K$가 주어졌을 때, 다음 조건에 맞는 집합 $S$의 개수를 $998\,244\,353$으로 나눈 나머지를 구하시오.

  • $S$의 모든 원소는 $K$의 배수가 아닌 $N$ 이하의 서로 다른 양의 정수이다.
  • $|S|$는 짝수이다.
  • $S$의 모든 원소의 합은 $N$이다.

입력

첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스마다, 한 줄에 두 정수 $N$, $K$가 주어진다.

출력

각 테스트 케이스의 답을 한 줄에 한 개씩 출력한다.

제한

  • $1 \le T \le 10^{4}$
  • $0 \le K \le N \le 4\,000$

예제 입력 1

5
0 0
5 0
6 3
4 1
7 7

예제 출력 1

1
2
2
0
3

첫 번째 테스트 케이스는 $N=0$, $K=0$인 경우 $S=\emptyset$일 때만 조건을 만족한다.

두 번째 테스트 케이스는 $K=0$인 경우 $0$의 배수인 자연수는 존재하지 않으므로, $S$가 $\{1,\,4\}$, $\{2,\,3\}$일 때 조건을 만족한다.

세 번째 테스트 케이스는 $S$가 $\{1,\,5\}$, $\{2,\,4\}$일 때 조건을 만족한다.

네 번째 테스트 케이스에서 $K=1$이므로 자연수가 포함될 수 없고, $S=\emptyset$이면 합이 $N$이 되지 않으므로 만족하는 집합 $S$는 존재하지 않는다.

다섯 번째 테스트 케이스에서 $S$가 $\{1,\,6\}$, $\{2,\,5\}$, $\{3,\,4\}$일 때 조건을 만족한다.

출처

School > 경기과학고등학교 > 2023 GSHS CS Seminar D번