#5234. [Lydsy2017省队十连测]不好不坏题

内存限制:128 MiB 时间限制:30 Sec

题目描述

每个人心中对于不好不坏题的定义不同,对于小火车来说所谓的不好不坏题就是不那么有趣的题。
我们定义一个函数Wu(n)表示n的因子和,例如4有因子1,2,4所以Wu(4)=7。而S(n,k)表示所有不超过n的且满足Wu函
数值为k的倍数的数之和,例如S(20,7)=49,因为Wu(4),Wu(12),Wu(13), Wu(20)均为7的倍数。
给定n和p,求S(n,p)的值。

输入格式

一行两个整数n和p

输出格式

一行一个整数表示答案,对1000000007取模。
n<=10000000000,p=2或2017,p的取值在每个部分中平均分布。

样例

样例输入


			
1000000 2017

样例输出


			
150850429

数据范围与提示