시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 162 57 53 43.443%

문제

많은 프로그래밍 언어에서는 정수에 대해 다음과 같은 두 개의 단항 연산을 지원한다.

  • -x: x의 부호를 바꾼다. x의 값이 0인 경우는 값이 변하지 않는다.
  • ~x: x의 모든 비트를 뒤집는다. 예를 들어 x의 2진수 표현이 0000 1010일 경우 ~x1111 0101이 된다.

편의상 이 문제에서 다루는 프로그래밍 언어에서는 정수를 무한히 많은 비트로 표현하며, 음수를 나타낼 때 2의 보수 표현법(음수를 표현할 때 무한히 큰 2의 거듭제곱에서 그 수를 뺀 값으로 나타내는 표현법)을 쓴다고 가정한다. 이때 ~x의 연산 결과는 -x-1과 같다.

연산 10진법 2진법
x 10 0000 1010
-x -10 1111 0110
~x -11 1111 0101

x의 값이 10인 경우의 예시

정수 0에 위의 두 연산을 총 N번 적용해서 정수 M을 만들고자 할 때, 가능한 연산 순서의 가짓수를 구하여라.

입력

첫 줄에 연산 횟수를 의미하는 정수 N과 만들고자 하는 정수 M(0 ≤ N ≤ 300,000, -300,000 ≤ M ≤ 300,000)이 주어진다.

출력

첫 줄에 정수 0에 N번의 연산을 적용하여 M을 만드는 방법의 가짓수를 998,244,353으로 나눈 나머지를 출력한다.

예제 입력 1

4 0

예제 출력 1

6

예제 입력 2

7 -3

예제 출력 2

7

노트

1번 예시의 경우 ----0, --~~0, -~~-0, ~--~0, ~~--0, ~~~~0의 6가지 경우가 존재한다.

2번 예시의 경우 --~-~-~0, ~---~-~0, ~-~---~0, ~-~-~--0, ~-~-~~~0, ~-~~~-~0, ~~~-~-~0의 7가지 경우가 존재한다.