Public Judge

pjudge

Time Limit: 0.5 s Memory Limit: 512 MB Total points: 100 Hackable ✓
统计

给定正整数 $N,M$,已知有 $N$ 对不同的括号,将其任意排列得到一个括号序列,共有 $(2N)!$ 种排列方法。

称一个括号序列是合法的,当且仅当每对括号的下标之差都不是 $M$ 的倍数。

求合法括号序列的数量模 $10^9+7$ 的值。

输入格式

一行,两个正整数 $N,M$。

输出格式

一行,一个非负整数,表示答案。

样例 1

input

1 1

output

0

样例 2

input

3 2

output

288

样例 3

input

300 300

output

929890502

样例 4

input

100 23

output

171243255

样例 5

input

2000 1000

output

348739341

数据范围

对于所有数据,$M\le N\le 2000$。

子任务编号 $N\le$ 分数
$1$ $5$ $9$
$2$ $100$ $12$
$3$ $300$ $13$
$4$ $900$ $18$
$5$ $2000$ $48$

时间限制:$\texttt{0.5s}$

空间限制:$\texttt{512MB}$