Count Good Arrangements of Stones

There are N green stones labeled 1 through N and N gray stones labeled 1 through N. All 2N stones are arranged in a row (each two adjacent positions are at distance 1). For each label i (1 ≤ i ≤ N), let \(\mathrm{dist}(i)\) denote the absolute difference between the positions of the green stone with label \(i\) and the gray stone with label \(i\). Given a positive integer M, an arrangement is called bad if there exists at least one i such that \(M\) divides \(|\mathrm{dist}(i)|\) (i.e. \(M\mid \mathrm{dist}(i)\)); otherwise, the arrangement is good.

The task is to compute the number of good arrangements modulo \(10^9+7\). Two arrangements are considered identical only if the sequence of stones (including both color and label) is exactly the same.

Mathematical Formulation:
Let L = 2N. For each label \(1\le i\le N\), if the positions of its two stones are \(p\) and \(q\) then
\[ \mathrm{dist}(i) = |p-q|. \]
An arrangement is bad if for at least one \(i\),
\[ M \mid |p-q|, \]
and good otherwise. The answer is the total number of good arrangements modulo \(10^9+7\).

Hint: Use the inclusion–exclusion principle. For each pair \(i\), let \(A_i\) be the event that \(M\) divides \(\mathrm{dist}(i)\). Then, the number of good arrangements equals
\[ \sum_{r=0}^{N} (-1)^r \cdot (\text{number of ways to choose } r \text{ disjoint bad pairs}) \cdot 2^r \cdot (L-2r)!\;\mod (10^9+7). \]

inputFormat

The input consists of a single line containing two space‐separated integers N and M (1 ≤ N, M ≤ ...). N represents the number of stones for each color, and M is the divisor used in the condition.

outputFormat

Output a single integer — the number of good arrangements modulo \(10^9+7\).

sample

1 1

0