Even‐Parity Canonical Music

In a twist on the famous canon, a new musical notation is invented. There are n distinct pitches and a music piece is composed of m segments. Each segment is a nonempty harmony – a nonempty subset of the n pitches. Two segments must have different pitch‐sets, and two music pieces are considered the same if one can be obtained from the other by reordering the segments.

In addition, to impose some regularity, it is required that in the entire piece each pitch is sounded an even number of times. In other words, if we represent each segment as a vector in \(\mathbb{F}_2^n\) (with 1 indicating the pitch is used), then the bitwise sum (mod 2) of the m chosen distinct nonzero vectors must be the zero vector.

The task is to count, modulo \(10^8+7\), the number of different music pieces with exactly m segments that satisfy these conditions.

Note: The order of segments does not matter. For example, the pieces \(\{\{1,2\},\{2,3\}\}\) and \(\{\{2,3\},\{1,2\}\}\) are considered identical.

Mathematical formulation:

Let \(T = \{S \subseteq \{1,2,\dots,n\} : S\neq\emptyset\}\) (so \(|T|=2^n-1\)). We want to count the number of sets \(X\subset T\) with \(|X|=m\) such that \[ \bigoplus_{S\in X} \chi_S = 0\quad\text{(in }\mathbb{F}_2^n\text{)}, \] where \(\chi_S\) is the characteristic vector of subset \(S\). The answer should be computed modulo \(10^8+7\).

A useful derivation uses the orthogonality of characters. One may show that the answer equals \[ \frac{1}{2^n}\Biggl[ \binom{2^n-1}{m} + (2^n-1)\,g(m) \Biggr] \pmod{10^8+7}, \] where \[ g(m)=\begin{cases} (-1)^{m/2}\,\binom{2^{n-1}-1}{m/2}, & \text{if } m \text{ is even},\\[1mm] -(-1)^{(m-1)/2}\,\binom{2^{n-1}-1}{(m-1)/2}, & \text{if } m \text{ is odd}. \end{cases} \] However, you only need to output the final count modulo \(10^8+7\).

inputFormat

The input consists of a single line containing two integers n and m (with 1 ≤ n, 1 ≤ m ≤ 2ⁿ−1), where n is the number of distinct pitches and m is the number of segments.

outputFormat

Output a single integer – the number of valid music pieces modulo \(10^8+7\).

sample

1 1

0