时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
企鹅喜欢收集石头，他有 
个编号不同的石头，编号分别为 
到 。现在企鹅想从这 个石头中选出 
个石头带回家。但是，企鹅认为如果选出的 个石头的编号的最大公约数（
）为 ，这些石头就会打架。为了防止石头打架，企鹅想知道有多少种选择石头的方案满足选出的 个石头的编号的 不为 。（假如选了 
个石头，分别是 、
、
，那么 %20%3D%201)
。）由于方案数可能很大，请对 
取模。（easy 版本和 hard 版本仅数据范围不同。）
注：只选定一个石头，则最大公约数视为这个石头的编号本身。
输入描述:
第一行包含两个整数和
（
，且
）。
输出描述:
输出一个整数，表示满足条件的方案数，对取模。