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ń.