16122번 - Unary

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

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

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

x의 값이 10인 경우의 예시

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

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

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

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

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