Unary

Interview

Time limit1sMemory limit512 MB

Summary

Count length-N strings of negation and bitwise-NOT that map 0 to M in two's complement, modulo 998244353.

Level: Medium7 of 10
Topics: Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

Many programming languages support the following two unary operations on integers.

-x: flips the sign of x. If the value of x is 0, the value does not change.
~x: flips every bit of x. For example, if the binary representation of x is 0000 1010, then ~x is 1111 0101.

For convenience, the programming language used in this problem represents integers with infinitely many bits, and represents negative numbers in two's complement (a negative number is written as an infinitely large power of two minus that number). Under this representation, the result of ~x equals -x-1.

Operation	Decimal	Binary
`x`	`10`	`0000 1010`
`-x`	`-10`	`1111 0110`
`~x`	`-11`	`1111 0101`

Example for the value x = 10

Given that we apply the two operations above to the integer 0 a total of N times to obtain the integer M, find the number of possible operation orders.

Input

The first line gives the integer N, the number of operations, and the integer M to be obtained (0 ≤ N ≤ 300,000, -300,000 ≤ M ≤ 300,000).

Output

On the first line, print the number of ways to apply N operations to the integer 0 to obtain M, modulo 998,244,353.

Hint

For sample 1, there are 6 cases: ----0, --~~0, -~~-0, ~--~0, ~~--0, ~~~~0.

For sample 2, there are 7 cases: --~-~-~0, ~---~-~0, ~-~---~0, ~-~-~--0, ~-~-~~~0, ~-~~~-~0, ~~~-~-~0.

Examples2

Example 1
Input
```
4 0
```
Expected output
```
6
```
Example 2
Input
```
7 -3
```
Expected output
```
7
```