D. GukiZ и двоичные операции
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Все мы знаем, что GukiZ часто играет с массивами.

Сейчас она размышляет над следующим вопросом: сколько существует массивов a длины n, состоящих из неотрицательных целых чисел строго меньше 2l, удовлетворяющих условию ? Здесь операция означает побитовое И (в языке Pascal она обозначается как and, на языке C/C++/Java/Python она обозначается как &), операция означает побитовое ИЛИ (на языке Pascal она обозначается как , наC/C++/Java/Python она обозначается |).

Так как ответ может быть достаточно большим, посчитайте его по модулю m. В этот раз GukiZ не придумал решения и ему нужно, чтобы вы помогли ему!

Входные данные

В первой и единственной строке входа записано четыре целых числа n, k, l, m (2 ≤ n ≤ 1018, 0 ≤ k ≤ 1018, 0 ≤ l ≤ 64, 1 ≤ m ≤ 109 + 7).

Выходные данные

В единственной строке выведите количество массивов, удовлетворяющих данному выше условию, по модулю m.

Примеры
Входные данные
2 1 2 10
Выходные данные
3
Входные данные
2 1 1 3
Выходные данные
1
Входные данные
3 3 2 10
Выходные данные
9
Примечание

В первом примере подходящие массивы таковы: {1, 1}, {3, 1}, {1, 3}.

Во втором примере единственный подходящий массив: {1, 1}.

В третьем примере подходящие массивы: {0, 3, 3}, {1, 3, 2}, {1, 3, 3}, {2, 3, 1}, {2, 3, 3}, {3, 3, 0}, {3, 3, 1}, {3, 3, 2}, {3, 3, 3}.