Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P162SUMF - Round 2F - AND hay là OR

AND (&) và OR(|) là 2 phép toán bit cơ bản. Lúi có một tập hợp gồm các số nguyên không âm và nhỏ hơn 2^l. Giờ Lúi phải chọn ra từ tập số nguyên trên n số (các số có thể trùng nhau) sao cho (a1 & a2) | (a2 & a3) | … | (an-1 & an) == k.

Vậy Lúi có bao nhiêu cách để chọn :/ Vì số cách là một số rất lớn nên ta sẽ lấy modulo m.

Input

Dòng đầu số nguyên n, k, l, m (2<=n<=10^18, 0<=k<=10^18, 0<=l<= 64, 1<=m<= 10^9 + 7).

Output

Số nguyên duy nhất là kết quả bài toán sau khi đã được lấy modulo m

Example

Input:
3 3 2 10

Output:
9

Giải thích:

Có các cách chọn sau: {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}.


Được gửi lên bởi:adm
Ngày:2016-07-14
Thời gian chạy:1s-2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.