Winning Chocolate Splits

In this game, there are \(N+1\) chocolates. For \(i=1,2,\dots,N\) the \(i\)th chocolate has exactly \(i\) pieces, and the extra chocolate (the \(N+1\)th one) has \(M\) pieces.

The players \(I\) and \(J\) take turns making moves (with \(I\) moving first). A move consists of selecting one chocolate (which is a pile of pieces) and splitting it into three ordered segments: left, middle, and right such that:

• Each segment has an integer number of pieces.
• The middle segment is nonempty (i.e. at least 1 piece).
• The left and right segments can be empty (i.e. 0 pieces).

After splitting, the middle segment is immediately eaten while the left and right segments (if nonempty) are returned as separate chocolates for future moves. A player loses if, when it is his turn, there is no chocolate left.

The twist is that player \(I\) (the first player) makes his very first move uniformly at random among all his legal moves. Immediately after that, he computes the winning strategy and plays optimally. Meanwhile, player \(J\) always plays optimally.

Your task is to count, modulo \(10^9+7\), the number of first moves available to player \(I\) that eventually guarantee a win for him.

Two moves are considered different if they either choose a different chocolate or if the ordered triple (i.e. the number of pieces in the left, middle, and right segments) is different.

---

Game Theoretic Analysis

The game is impartial and can be analyzed by computing the Grundy number (or nimber) for a chocolate of a given size. In fact, by a simple induction one may prove that the Grundy value \(g(n)\) for a chocolate with \(n\) pieces is \(n\) (with the convention \(g(0)=0\), i.e. an empty chocolate is not playable).

For a move applied to a chocolate of size \(n\) which splits it into segments with \(L\), \(M\), and \(R\) pieces (with \(M\ge1\) and \(L,R\ge0\) such that \(L+M+R=n\)), the resulting nim‐value will be the XOR of the nim‐values of the remaining chocolates. Since \(g(n)=n\), the new position has nim‐value:

[ \text{nim-sum} = (S \oplus n) \oplus (L \oplus R), ]

where \(S\) is the XOR of the Grundy values of all other chocolates in the initial configuration, i.e.,

[ S = (1 \oplus 2 \oplus \cdots \oplus N) \oplus M. ]

For a first move on a chocolate of size \(n\) to be winning, the move must yield a position with nim-sum \(0\). That is, if the chosen chocolate has size \(n\) and we split it into parts \(L,M,R\) (with \(M=n-L-R\) and \(M\ge1\)), we need:

[ (S \oplus n) \oplus (L \oplus R) = 0 \quad\Longleftrightarrow\quad L \oplus R = n \oplus S. ]

Thus for a chocolate of size \(n\), let \(K = n \oplus S\). We now must count the number of ways to choose nonnegative integers \(L\) and \(R\) satisfying:

• \(L+R \le n-1\) (since the middle part \(M=n-L-R\ge1\)), and
• \(L \oplus R = K\).

This count (multiplied by \(2^{\text{popcount}(K)}\), explained below) gives the number of winning moves on that chocolate. (A more detailed explanation involves noting that for a fixed sum \(s=L+R\), the equation \(L+R = (L \oplus R) + 2(L\,\&\,R)\) forces \(s = K+2t\) for some \(t\ge0\), and a valid solution exists only when \(t \& K = 0\). Then one sums over \(s\) from \(K\) to \(n-1\) with steps of 2.)

The final answer is the sum of winning moves for each chocolate in the initial configuration (i.e. for sizes \(1,2,\dots,N\) and an extra chocolate of size \(M\)), all taken modulo \(10^9+7\).

inputFormat

The input consists of a single line containing two integers \(N\) and \(M\) (where \(N\) denotes the number of chocolates with sizes \(1\) to \(N\), and \(M\) is the number of pieces in the extra chocolate).

outputFormat

Output a single integer, the number of winning first moves for player \(I\) modulo \(10^9+7\).

sample

1 1

0