简单的数学题

题目描述

由于出题人懒得写背景了,题目还是简单一点好。 输入一个整数n和一个整数p,你需要求出$(\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j))~mod~p$,其中gcd(a,b)表示a与b的最大公约数。 **刚才题面打错了,已修改**

输入输出格式

输入格式


一行两个整数p、n。

输出格式


一行一个整数$(\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j))~mod~p$。

输入输出样例

输入样例 #1

998244353 2000

输出样例 #1

883968974

说明

对于20%的数据,$n \leq 1000$。 对于30%的数据,$n \leq 5000$。 对于60%的数据,$n \leq 10^6$,时限1s。 对于另外20%的数据,$n \leq 10^9$,时限3s。 对于最后20%的数据,$n \leq 10^{10}$,时限6s。 对于100%的数据,$5 \times 10^8 \leq p \leq 1.1 \times 10^9$且p为质数。