Winning Initial Configurations

Alice and Bob are about to play a game on a 1×n board. Initially, there are m coins placed on the board such that each coin occupies a distinct cell. The cells are numbered from 1 to n and no cell contains more than one coin.

The players take turns, with Alice playing first. On each turn, the current player chooses one coin and moves it any number of cells to the left (at least one cell). However, the coin may not be moved off the board and it may not jump over another coin.

The game ends when the current player has no valid moves. Notice that when all m coins occupy the leftmost m cells (i.e. positions 1, 2, …, m) no coin can be moved further; in that case the player whose turn it is loses.

It turns out that if both players play optimally, some initial configurations guarantee a win for Alice, and some do not. In fact, by a standard game‐theoretic analysis the move options from a configuration p₁ < p₂ < … < p_m can be mapped to a Nim heap whose size is given by p_i - i (for 1 ≤ i ≤ m). In other words, each configuration corresponds uniquely to an increasing sequence g₁, g₂, …, g_m where g_i = p_i - i and 0 ≤ g₁ < g₂ < … < g_m ≤ n - m. The nim-sum is the XOR of all these values. Alice can force a win if and only if the nim-sum is nonzero.

Your task is to count the number of initial coin placements (i.e. choices of m cells among n) for which the nim-sum is not zero. Since the answer can be huge, output it modulo $10^9+7$.

Note on the Transformation: Every valid configuration corresponds uniquely to a sequence {g₁, g₂, …, g_m} where g_i = p_i - i and the condition 0 ≤ g₁ < g₂ < … < g_m ≤ n - m holds. The total number of configurations is $\binom{n}{m}$, and your program must subtract those configurations in which the XOR of all g_i equals $0$.

inputFormat

The input consists of two space‐separated integers n and m, where n is the length of the board and m is the number of coins.

outputFormat

Output a single integer: the number of initial configurations that guarantee a win for Alice, modulo 1000000007.

sample

4 2

3