解题思路

本题要求统计满足三个条件的序列个数，可以使用动态规划进行计数。

设 dp[i][j] 表示：考虑了前 i 个位置（即 a_1, a_2, …, a_i），且这些位置上已选的数字之和模 n 的余数为 j 的方案数。

初始化：
dp[0][0] = 1，表示还没有选择任何数字时，和为 0，模 n 余 0，方案数为 1。

题目内容

小蓝定义了一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ 为“协调序列”，当且仅当同时满足以下三个条件：

1. 对于每个下标 $i$，有 $1 \le a_i \le m$；
2. $a_i$ 能够被 $i$ 整除；
3. $\sum_{i=1}^{n} a_i$ 是 $n$ 的整数倍。

给定正整数 $n$ 和 $m$，请你计算一共有多少个不同的协调序列。由于答案可能很大，请将结果对 $10^9+7$ 取模。

数据范围：$n$ 和 $m$ 均为不超过 1000 的正整数。

输入描述

输入包含一行，两个正整数 $n$ 和 $m$，用空格分隔。

输出描述

输出一个整数，表示协调序列的数量对 $10^9+7$ 取模后的结果。

样例1

输入

2 2

输出

1

说明

当 $n=2, m=2$ 时，协调序列长度为 2。第 1 项 $a_1$ 需满足 $1 \le a_1 \le 2$，即 $a_1 \in \{1, 2\}$；第 2 项 $a_2$ 需被 2 整除且不超过 2，所以 $a_2$ 只能为 2。序列总和为 $a_1 + 2$，需要是 $n=2$ 的倍数。若 $a_1=1$，总和为 3，不能被 2 整除；若 $a_1=2$，总和为 4，能被 2 整除。因此只有 $(2,2)$ 这一种序列，答案为 1。

样例2

输入

3 4

输出

3

说明

当 $n=3, m=4$ 时，序列长度为 3。第 1 项 $a_1 \in \{1,2,3,4\}$；第 2 项 $a_2$ 是 2 的倍数且 $\le 4$，故 $a_2 \in \{2,4\}$；第 3 项 $a_3$ 是 3 的倍数且 $\le 4$，故 $a_3$ 只能为 3。要求总和 $a_1+a_2+a_3$ 是 3 的倍数。 枚举所有组合：$(1,2,3)$ 总和为 6，满足；$(2,4,3)$ 总和为 9，满足；$(4,2,3)$ 总和为 9，满足；其余组合如 $(1,4,3)$ 等总和不被 3 整除。因此共有 3 个不同的协调序列，答案为 3。

样例3

输入

1 1

输出

1

说明

边界情况：当 $n=1, m=1$ 时，序列只有一项 $a_1$。条件要求 $1 \le a_1 \le m=1$，且 $a_1$ 必须被 1 整除。唯一取值为 $a_1=1$，总和 1 自然能被 $n=1$ 整除。因此协调序列只有 $(1)$ 一种，答案为 1。

样例4

输入

4 4

输出

2

说明

当 $n=4, m=4$ 时，序列长度为 4。各位置可能取值为：$a_1 \in \{1,2,3,4\}$；$a_2$ 是 2 的倍数且 $\le 4$，即 $a_2 \in \{2,4\}$；$a_3$ 是 3 的倍数且 $\le 4$，故 $a_3 = 3$；$a_4$ 是 4 的倍数且 $\le 4$，故 $a_4 = 4$。 总和 $S = a_1 + a_2 + 7$，需被 4 整除，即 $a_1 + a_2 \equiv 1 \pmod{4}$。当 $a_2=2$ 时，$a_1 \equiv 3 \pmod{4}$，$a_1$ 只能取 3；当 $a_2=4$ 时，$a_1 \equiv 1 \pmod{4}$，$a_1$ 只能取 1。因此满足条件的序列为 $(3,2,3,4)$ 和 $(1,4,3,4)$，共 2 个，答案为 2。