#P1192. 换位

换位

Description

教室里有n个同学从左到右坐在同一排,编号从左到右依次是1到n。 如果两个同学编号恰好相差1,说明这两个同学是同桌。 坐在一起时间长了,每个同学都与同桌有了深厚的感情。 现在老师要让同学们换位,老师为每个同学重新选择一个位置。众所周知一共有n!种换位方式。 如果一个同学换位后坐在了他以前的同桌的位置,那么他将是开心的。 现在老师想知道,有多少种换位方式能够使得开心的同学数恰好是m的倍数。

Input Format

一行两个正整数,分别是n和m。

Output Format

一行一个数,表示满足条件的换位方式的数量。由于数量会很多,对10^9+7取模。



3 2

4

Hint

【样例解释】

在1~3中2的倍数只有2本身,所以就是求2个同学开心的方式数量。

分别是 (1 3 2) (2 1 3) (2 3 1) (3 1 2)

共4个

【数据规模和约定】

对于30%的数据, 1<=m<=n<=10

对于60%的数据, 1<=m<=n<=50

对于100%的数据,1<=m<=n<=1000

Source

图上dp dp 月赛 地级