P17238 『STA - R10』Petal Dance

Aqua 给你两个正整数 $n,m$，你需要对每个整数 $1\le k\le n$ 求 $$a_k=\sum_{i=1}^n\sum_{j=1}^n\gcd(ij,k)$$ 的值。答案对 $m$ 取模。

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

因为输出太多不好，所以你只需要输出 $\displaystyle\bigoplus_{k = 1}^n \left( k \cdot (a_k\bmod m) \right)$ 的值就可以了（注意取模的位置）。

样例 1 解释： $\{a_k\} = \{100, 175, 202, 265, 244, 347, 214, 369, 340, 427\}$。 **本题采用捆绑测试。** | Subtask | 分值 | 特殊性质 | |:---:|:---:|:---:| | 1 | 5 | $n \le 500$ | | 2 | 5 | $m = 2$ | | 3 | 15 | $n \le 5\times 10^3$ | | 4 | 15 | $n \le 10^5$ | | 5 | 20 | $n \le 10^6$ | | 6 | 40 | 无 | 对于全部数据：$1\le n\le 5\times 10^6$，$1\le m \le 10^9$。