统计Perfect数组

题目描述

给定两个整数 $n$ 和 $m$，对于下标从 0 开始、长度为 $n$ 的正整数数组 $a$，只有满足如下条件，才能被称作是一个“Perfect数组”：

• 数组每一位上的值最大只能取到 $m$，即 $a[i]\in[1,m]\ (0\le i<n)$
• 从下标为 $1$ 的位置开始，数组每一位都可以被它的前一位整除，即 $a[i-1] \mid a[i] \ (0<i<n)$

对于给定的 $n$ 和 $m$，请你找到长度为 $n$ 的 不同 的Perfect数组的数目。由于答案可能很大，返回对 $10^9+7$ 取模的结果

输入格式

一行 $2$ 个整数 $n$ 和 $m$，$n$ 代表Perfect数组的长度，$m$ 代表数组上每一位的最大取值

输出格式

$1$ 个对 $10^9+7$ 取模的整数 $ans$

样例 #1

样例输入 #1

2 5

样例输出 #1

10

样例 #2

样例输入 #2

5 3

样例输出 #2

11

提示

数据范围与提示

「样例解释 #1」

存在以下Perfect数组：

• 以 $1$ 开头的数组（$5$ 个）：$[1,1]$、$[1,2]$、$[1,3]$、$[1,4]$、$[1,5]$
• 以 $2$ 开头的数组（$2$ 个）：$[2,2]$、$[2,4]$
• 以 $3$ 开头的数组（$1$ 个）：$[3,3]$
• 以 $4$ 开头的数组（$1$ 个）：$[4,4]$
• 以 $5$ 开头的数组（$1$ 个）：$[5,5]$

共计 $5 + 2 + 1 + 1 + 1 = 10$ 个不同Perfect数组

「样例解释 #2」

存在以下Perfect数组：

• 以 $1$ 开头的数组（$9$ 个）：
  • 不含其他不同值（$1$ 个）：$[1,1,1,1,1]$
  • 含一个不同值 $2$（$4$ 个）：$[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]$
  • 含一个不同值 $3$（$4$ 个）：$[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]$
• 以 $2$ 开头的数组（$1$ 个）：$[2,2,2,2,2]$
• 以 $3$ 开头的数组（$1$ 个）：$[3,3,3,3,3]$

共计 $9 + 1 + 1 = 11$ 个不同Perfect数组

「数据范围」

对于 $30\%$ 的数据，$2 \leq n \leq 100$，$1 \leq m \leq 100$

对于 $50\%$ 的数据，$2 \leq n \leq 1000$，$1 \leq m \leq 1000$

对于 $100\%$ 的数据，$2 \leq n \leq 10^4$，$1 \leq m \leq 10^4$

思考了$n$天的脑子终于废了