题目描述

小w想要解决一个有关整数的问题。

给定$n$，他想要知道$\sum_{k=1}^n \sum_{i=1}^k \sum_{j=1}^k \gcd(i,j,k)$对质数$mod$取模的值。

输入格式

从标准输入读入数据。

输入第一行包含两个正整数 $n,mod$。

输出格式

输出到标准输出。

输出一行一个整数，表示答案对$mod$取模的值。

样例

输入

50 998244353

输出

58514

子任务

对于$30\%$的数据，$n\le 100$。

对于$60\%$的数据，$n\le 10^7$。

对于$100\%$的数据，$n\le 10^9$。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载