#P15625. [2022年保加利亚国家队组队赛Junior]sequences

[2022年保加利亚国家队组队赛Junior]sequences

题目描述

给定两个正整数 nn 和 MXMX。

请计算有多少个长度为 nn 的正整数序列

a1,a2,…,ana_1,a_2,\ldots,a_n

满足:

1≤ai≤MX1\le a_i\le MX

且

gcd⁡(a1,a2,…,an)=1.\gcd(a_1,a_2,\ldots,a_n)=1.

答案需要对 1 000 000 0071\,000\,000\,007 取模。

输入格式

一行输入两个整数 n,MXn,MX。

输出格式

输出一行一个整数,表示满足条件的序列数量对 1 000 000 0071\,000\,000\,007 取模后的结果。

数据范围

1≤n,MX≤1091\le n,MX\le 10^9

并且每个 aia_i 满足:

1≤ai≤MX.1\le a_i\le MX.

样例

输入

3 8

输出

439

子任务

子任务 分值 附加限制
1 5 n,MX≤8n,MX\le 8
2 15 n,MX≤500n,MX\le 500
3 MX≤1000MX\le 1000
4 MX≤100000MX\le 100000
5 20 MX≤10000000MX\le 10000000
6 30 无附加限制

每个子任务独立计分。