问题描述

​ 定义一个长度为 $n$ 的序列 $\{a_i\}$ 的优美值为其所有元素最大公约数的约数个数。

​ 求所有满足对于任何 $i$， $1 \leqslant a_i \leqslant m$ 的不同序列的优美值的和对 $\texttt{10007}$ 取模的结果。定义两个序列 $a$, $b$ 不同当且仅当存在至少一个 $i$ 使得 $a_i \not= b_i$。

输入格式

​ 一行两个正整数 $n,\ m$。

输出格式

​ 一行一个正整数表示答案。

2 3

11

样例 2

​ 见目录下 non2.in/ans。该样例满足数据点 10-14 的性质。

样例 3

​ 见目录下 not3.in/ans。该样例满足数据点 18-20 的性质。

样例解释 1

有如下序列以及优美值：

1 1 : 1
1 2 : 1
1 3 : 1
2 1 : 1
2 2 : 2
2 3 : 1
3 1 : 1
3 2 : 1
3 3 : 2

它们的优美值和为 $11$。

数据规模与约定

请注意常数因子与模数对得分的影响。

大样例

大样例下载