Problem Description

Aqua gives you two positive integers $n, m$. For each integer $1 \le k \le n$, you need to compute

The answer should be taken modulo $m$.

Input Format

One line contains two positive integers $n, m$.

Output Format

Since the output would be too large, you only need to output the value of $\displaystyle\bigoplus_{k = 1}^n \left( k \cdot (a_k\bmod m) \right)$ (note where the modulo is applied).

10 998244353

7854

1000000 998244353

666900907572623

Hint

Explanation for Sample 1: $\{a_k\} = \{100, 175, 202, 265, 244, 347, 214, 369, 340, 427\}$.

This problem uses bundled testdata.

Constraints for all testdata: $1\le n\le 5\times 10^6$, $1\le m \le 10^9$.

Translated by ChatGPT 5