Число Белла $B_n$ обозначает количество способов разбиения $n$ пронумерованных элементов на непересекающиеся подмножества.
Для заданных $0\le n\le N$ вычислите $B_n \bmod p^k$. Вам необходимо вывести значение
$$ \bigoplus_{n=0}^N \left((B_n \bmod p^k)+C\right) $$
где $\bigoplus$ обозначает операцию побитового исключающего ИЛИ (XOR).
Иай знает, как решать задачу для $p\le 100$, но, изучив научные статьи, она также научилась решать её для $p\le 2.5\times 10^4$, однако в итоге решила ограничиться случаем $p\le 100$.
Входные данные
Вводятся $N,p,k,C$.
Выходные данные
Выведите ответ.
Примеры
Пример 1
Входные данные
10 5 2 0
Выходные данные
18
Примечание
$$B_{0,\dots,10}= [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975]$$
После взятия по модулю $25$ получаем $[1, 1, 2, 5, 15, 2, 3, 2, 15, 22, 0]$, их XOR-сумма равна $18$.
Пример 2
Входные данные
666 2 29 2003
Выходные данные
25147922
Подзадачи
Для $100\%$ данных гарантируется, что $0\le N\le 10^6$, $p\le 100$, $C,p^k\le 10^9$, где $p$ — простое число.
- Тесты $1\sim 4$: $N\le 10^3$.
- Тесты $5,6$: $N\le 5\times 10^4$.
- Тест $7$: $k=1, p\le 100$.
- Тест $8$: $k=1$.
- Тесты $9, 10$: $p^k\le 20$.
- Тесты $11\sim 18$: $p\le 100$.
- Тест $19$: $p\le 2\times 10^3$.
- Тест $20$: без дополнительных ограничений.