Dla każdego $k=1\dots n$ oblicz $k^0+k^1+\cdots+k^{m-1}$.
To zadanie wydaje się proste, ale Xiao Lan jest osobą dbającą o szczegóły. Dzisiaj musi wykonać obliczenia modulo $M$.
Wejście
Wczytaj trzy liczby całkowite dodatnie $n, m, M$, zgodnie z treścią zadania.
Wyjście
Niech $a_k$ oznacza wynik dla danego $k$. Wyprowadź $a_1 \oplus a_2 \oplus \cdots \oplus a_n$, gdzie $\oplus$ oznacza operację bitową XOR.
Przykład
Przykład 1
Wejście
10 4 1000
Wyjście
363
Uwagi
Wyniki przed wykonaniem operacji modulo to $[4, 15, 40, 85, 156, 259, 400, 585, 820, 1111]$, a po wykonaniu operacji modulo to $[4, 15, 40, 85, 156, 259, 400, 585, 820, 111]$.
Podzadania
Dla $100\%$ danych wejściowych zachodzą ograniczenia: $1\le n\le 10^7; 1\le m\le 10^{10^6}; 2\le M\le 10^{9}$.
| Numer testu | $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$ | jest liczbą pierwszą | |
| $13,14$ | $10^9$ | ||
| $15,16$ | $10^5$ | ||
| $17$ | $10^6$ | ||
| $18,19$ | $=998244353$ | ||
| $20,21$ | jest liczbą pierwszą | ||
| $22$ | $\mu(M)^2=1$ | ||
| $23,24$ | $=2^k$ | ||
| $25$ |
Puste pola oznaczają, że obowiązują jedynie ograniczenia dla $100\%$ danych. $\mu(M)$ to funkcja Möbiusa.
Standardowy algorytm dla tego zadania nie wymaga użycia __int128, proszę o rozwagę.