302846: CF551D. GukiZ and Binary Operations

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

GukiZ and Binary Operations

题意翻译

求有多少个由n个严格小于2^l的自然数组成的数列a满足(a 1&a2)|(a 2&a 3)|......|(a n-1&a n)=k 答案对m取模 输入包括一行n,k,l,m 输出一行,即答案

题目描述

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: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF551D/a6e7bc576316f94114c2b7ddad7b1f99dc329174.png)? Here operation ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF551D/620e07dca4a112648a0a9f81b5fb9f226c4bb233.png) means bitwise AND (in Pascal it is equivalent to and, in C/C++/Java/Python it is equivalent to &), operation ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF551D/6bfd82b83489db5433e1a03d2bc0f44671a33056.png) means bitwise OR (in Pascal it is equivalent to ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF551D/6bfd82b83489db5433e1a03d2bc0f44671a33056.png), 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} $ .

Input

题意翻译

求有多少个由n个严格小于2^l的自然数组成的数列a满足(a 1&a2)|(a 2&a 3)|......|(a n-1&a n)=k 答案对m取模 输入包括一行n,k,l,m 输出一行,即答案

加入题单

算法标签: