8608: Steins;Game 2

Have you ever heard of the Nim game? Probably your answer is yes, but I bet you've never heard a new game called ``Steins;Game''! The game is named so because it is a game played with many piles of stones, and Stein means stone in German.

Alice and Bob want to play this game now. The game is played as follows:

There are n piles of stones arranged in a row. The i-th pile consists of a_i(a_i≥0,a_i=0 means this pile is empty$)$ stones. It is guaranteed that 0≤a₁≤a₂≤⋯≤a_n, i.e., the number of stones in each pile is nondecreasing. Starting with Alice, the two players take turns doing the following operation:

•  Take any positive number of stones from some pile(the number of stones taken must not exceed the current number of stones in the pile), such that after the operation, it still holds that the number of stones in each pile is nondecreasing.

The game ends when either player cannot make a valid move, and the player who cannot make a move loses and the other player wins.

Now that Bob has bribed the referee to get the chance to set the initial number of stones by himself. He wonders, how many ways are there to set the initial number of stones, such that the size of the largest pile doesn't exceed $m$, and he can win the game under two players' optimal strategy?

Since the answer may be too large, you only need to output it modulo 998244353.

The input consists of one line containing two integers n,m(1≤n≤40000,0≤m≤10¹²), denoting the number of piles and the upper bound on the size of the largest pile, respectively.

Output an integer in one line, denoting the answer taken modulo 998244353.

2 2

3

For the first sample test, the valid initial number of stones such that Bob can win the game under two players' optimal strategy are [0,0],[1,1] and [2,2].