Problem Brief

Count Integer Sequences

INTERNOA

Print the number of integer sequences of length N, A = {A1, A2, A3...., AN} possible where the Sequence A should follow the conditions below:

All elements in A should be between 0 and M (inclusive)
XOR of all the elements in A is equal to X

Print the number of integer sequence satisfying these conditions modulo 998244353.

Input Format:

N, M , X

Function Description

Complete the function countIntegerSequences in the editor.

countIntegerSequences has the following parameters:

N: the length of the sequence
M: the maximum value of the elements in the sequence
X: the XOR value to be achieved

Returns

int: the number of integer sequences modulo 998244353

1Example 1

Input

N = 200, M = 9000606388L, X = 317329110

Output

788002104

Explanation

The output is the number of integer sequences of length N that satisfy the given conditions modulo 998244353.

2Example 2

Input

N = 3, M = 3, X = 2

Output

Explanation

The 5 sequences of length N(3) that satisfy both the conditions are: (0, 0, 2), (0, 1, 3), (1, 1 ,2), (2, 2, 2), (2, 3, 3). All the sequences are of length N(3), all the elements in the sequence are between 0 and M(3) inclusive and xor of all the elements in the individual sequence is equal to X(2).