Logo CSP.ac

CSP.ac

1 s / 256 MB

#126. 【冬令营】Day3T3-换位

统计

【问题描述】

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

【输入格式】

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

【输出格式】

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

【样例输入1】

3 2

【样例输出1】

4

【样例解释1】

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

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

共4个

【样例输入2】

4 2

【样例输出2】

11

【数据规模和约定】

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

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

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