CF551D.GukiZ and Binary Operations

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

We all know that GukiZ often plays with arrays.

Now he is thinking about this problem: how many arrays $a$ , of length $n$ , with non-negative elements strictly less then $2^{l}$ meet the following condition: ? Here operation means bitwise AND (in Pascal it is equivalent to and, in C/C++/Java/Python it is equivalent to &), operation means bitwise OR (in Pascal it is equivalent to , in C/C++/Java/Python it is equivalent to |).

Because the answer can be quite large, calculate it modulo $m$ . This time GukiZ hasn't come up with solution, and needs you to help him!

输入格式

First and the only line of input contains four integers $n$ , $k$ , $l$ , $m$ ( $2<=n<=10^{18}$ , $0<=k<=10^{18}$ , $0<=l<=64$ , $1<=m<=10^{9}+7$ ).

输出格式

In the single line print the number of arrays satisfying the condition above modulo $m$ .

输入输出样例

输入#1
```
2 1 2 10
```
输出#1
```
3
```
输入#2
```
2 1 1 3
```
输出#2
```
1
```
输入#3
```
3 3 2 10
```
输出#3
```
9
```

说明/提示

In the first sample, satisfying arrays are ${1,1},{3,1},{1,3}$ .

In the second sample, only satisfying array is ${1,1}$ .

In the third sample, satisfying arrays are ${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}$ .

首页