Overflow is playing a domino game, which involves covering an $n \times m$ chessboard with L-shaped dominoes (the shape of the domino is shown in the figure below). After some research, he felt it was too simple and lacked challenge, so he came up with a new problem: how many ways are there to tile the entire chessboard with these dominoes without any overlap or gaps?

After further research, he found this problem too difficult to calculate. Therefore, he asks you to design an algorithm to solve it.

All dominoes are considered equivalent. Two tiling schemes are considered the same if and only if the final patterns are identical; rotational symmetry is not considered.

Since the answer may be very large, please output it modulo $998244353$.

Four orientations of the L-shaped domino.

Input

A single line containing two integers $n, m$ ($1 \le n \le 6, 1 \le m \le 10^{18}$).

Output

A single line containing a natural number representing the answer.

Examples

Input 1

3 4

Output 1

4