Сяо Лань хочет для каждого $k=1\dots n$ вычислить значение $k^0+k^1+\cdots+k^{m-1}$.
Эта задача кажется ничем не примечательной, но Сяо Лань — человек, который ценит точность и внимание к деталям. Сегодня она хочет вычислить результат по модулю $M$.
Входные данные
Входные данные содержат три целых положительных числа $n, m, M$, как описано в условии.
Выходные данные
Пусть $a_k$ — ответ для конкретного $k$. Выведите $a_1 \oplus a_2 \oplus \cdots \oplus a_n$, где $\oplus$ обозначает операцию побитового исключающего ИЛИ (xor).
Примеры
Пример 1
Входные данные
10 4 1000
Выходные данные
363
Пояснение к примеру 1
Ответы до взятия по модулю: $[4, 15, 40, 85, 156, 259, 400, 585, 820, 1111]$, ответы после взятия по модулю: $[4, 15, 40, 85, 156, 259, 400, 585, 820, 111]$.
Подзадачи
Для $100\%$ данных гарантируется, что $1\le n\le 10^7; 1\le m\le 10^{10^6}; 2\le M\le 10^{9}$.
| Номер теста | $n\le$ | $m\le$ | $M$ |
|---|---|---|---|
| $1,2$ | $10^3$ | $10^3$ | |
| $3\sim 5$ | $10^5$ | $10^9$ | |
| $6\sim 8$ | $10^6$ | $10^9$ | |
| $9,10$ | $10^9$ | $=998244353$ | |
| $11,12$ | $10^9$ | является простым | |
| $13,14$ | $10^9$ | ||
| $15,16$ | $10^5$ | ||
| $17$ | $10^6$ | ||
| $18,19$ | $=998244353$ | ||
| $20,21$ | является простым | ||
| $22$ | $\mu(M)^2=1$ | ||
| $23,24$ | $=2^k$ | ||
| $25$ |
Пустые ячейки означают, что на них распространяются только общие ограничения $100\%$ данных. $\mu(M)$ — функция Мёбиуса.
Стандартное решение этой задачи не требует использования __int128, пожалуйста, учитывайте это при реализации.