题目描述

小红最近一直在学习数组，突然有了一个想法，他定义了一个“特别数组”，当且仅当满足以下三个条件:

1. 对于$1 \leq i \leq n，有1 \leq a_i \leq m$
2. 对于$1 \leq i \leq n$保证$a_i$是$i$的倍数。
3. $a_1+a_2+....+a_n$是$n$的倍数。

现在给出$n$和$m$的值，请你求出满足条件的“特别数组”数量。由于答案可能过大，请对$10^9+ 7$取模。

输入描述

两个正整数$n$和$m$，用空格隔开。

$1 \leq n,m \leq 1000$

输出描述

特别数组的数量，答案对$10^9+ 7$取模。

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

3 5

输出

4

说明

$[1,2,3],[4,2,3],[2,4,3],[5,4,3]$共有以上四个好数组

思路：动态规划题

给出n和m的值，要求求出一个"特别数组"的数量，并对1e9+7取模

其实并没有什么其他好计算的办法，那么就想到动态规划能否解决问题，首先n和m的范围都在1000以内，那么代表支持$O(n^2logn)$的时间复杂度，那么dp的第一维肯定是我们有多少个数，另外"特别数组"是所有数加起来是n的倍数，也就是说模n为0，那么第二维就可以设置成当前所有数加起来模n为多少

所以我们设dp[i][j]，表示当前一共有i个数并且所有数加起来模n为j的数组的数量，那么在转移的时候可以枚举i与j和当前最后一个数是多少，最后一位数一定是i的倍数，所以我们可以用一个调和级数的时间复杂度去枚举它，最后答案即为dp[n][0]

转移方程为