| Codeforces Round 307 (Div. 2) |
|---|
| Закончено |
Все мы знаем, что 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}.
