Liczba Bella $B_n$ oznacza liczbę sposobów podziału $n$ ponumerowanych kul na $n$ nieuporządkowanych zbiorów.
Dla każdego $0\le n\le N$ oblicz $B_n \bmod p^k$. Wystarczy, że wypiszesz:
$$ \bigoplus_{n=0}^N \left((B_n \bmod p^k)+C\right) $$
gdzie $\bigoplus$ oznacza sumę XOR.
Yi'ai zna rozwiązanie dla $p\le 100$, ale po przejrzeniu literatury opanowała również przypadek $p\le 2.5\times 10^4$, jednak ostatecznie zdecydowała się ograniczyć zadanie do $p\le 100$.
Wejście
Wczytaj $N,p,k,C$.
Wyjście
Wypisz wynik.
Przykład
Przykład 1
Wejście:
10 5 2 0
Wyjście:
18
Uwagi do przykładu 1
$$B_{0,\dots,10}= [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975]$$
Po wzięciu modulo $25$ otrzymujemy $[1, 1, 2, 5, 15, 2, 3, 2, 15, 22, 0]$, a ich suma XOR wynosi $18$.
Przykład 2
Wejście:
666 2 29 2003
Wyjście:
25147922
Podzadania
Dla $100\%$ danych wejściowych zachodzą warunki $0\le N\le 10^6$, $p\le 100$, $C,p^k\le 10^9$, gdzie $p$ jest liczbą pierwszą.
- Testy $1\sim 4$: $N\le 10^3$.
- Testy $5,6$: $N\le 5\times 10^4$.
- Test $7$: $k=1, p\le 100$.
- Test $8$: $k=1$.
- Testy $9, 10$: $p^k\le 20$.
- Testy $11\sim 18$: $p\le 100$.
- Test $19$: $p\le 2\times 10^3$.
- Test $20$: brak dodatkowych ograniczeń.