2024年东华大学与昭通学院联合程序设计竞赛

E. 杰の序列

单点时限: 1.0 sec

内存限制: 512 MB

杰:我的房子还蛮大的,要是玩(写题)累了可以直接睡觉,没问题的。

众所周知,杰哥非常喜欢钻研数学,今天他给你了一道非常刺激的新题,希望你能解决。

对于一个包含 $n$ 个正整数的序列 $a_i$ ,若满足:

  1. 对于任意正整数 $i (i \leq n)$ ,满足 $a_i \in [1, m]$ 。
  2. 对于任意正整数 $i(i < n)$ ,满足 $a_i > a_{i + 1}$ 或 $\gcd(a_i, a_{i + 1}) \neq 1$ 。

则称之为 杰の序列

给定 $n,m$ ,求有多少不同的 杰の序列 ,答案模 $10^9+7$ 。两个序列存在一个位置不同,则视为不同的序列。

输入格式

一行两个数, $n, m(1 \leq n \leq 1000, 1\leq m \leq 10000)$

输出格式

一行一个数,表示答案

样例

Input
3 4
Output
23
Input
100 10000
Output
160839892