题目描述

小A在参加数学考试，有一道数学题让他很苦恼，他希望你来帮帮他解决这道题？

题目是这样的：输入一个整数 $n$ 和一个整数 $m$ ，你需要求出：

$$\left(\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n}\,i j \,\gcd (i,j)\right)\text {mod } m $$

其中 $\gcd(a,b)$ 表示 $a$ 与 $b$ 的最大公约数。

输入格式

一行两个整数 $m,n$ 。

一行一个整数表示答案。

998244353 2000

883968974

对于 $20\%$ 的数据， $n≤10^3$ 。

对于 $30\%$ 的数据， $n≤5×10^3$ 。

对于 $60\%$ 的数据， $n≤10^6$ 。

对于 $100\%$ 的数据， $n \le 10^{10},5×10^8≤m≤1.1×10^9$ ，且 $m$ 为质数。