← 返回题目列表

Codeforces · 551/D

D. GukiZ 和二元运算

中文机器翻译题面 查看原题

我们都知道GukiZ经常玩数组。

现在他在思考这个问题:有多少个长度为 n、非负元素严格小于 2l 的数组 a 满足以下条件: $$(a_{1}\ \mathrm{and}\ a_{2})\ \mathrm{or}\ (a_{2}\ \mathrm{and}\ a_{3})\ \mathrm{or}\ldots\ \mathrm{或}\ (a_{n-1}\ \mathrm{and}\ a_{n})=k$$?这里$$\text{and}$$表示按位与(在Pascal中相当于and,在C/C++/Java/Python中相当于&),操作$$\sigma_{1}^{2}$$表示按位或(在Pascal中相当于$$\sigma_{1}^{2}$$,在C/C++/Java/Python中相当于|)。

因为答案可能相当大,所以以 m 为模进行计算。这次GukiZ还没有想出解决办法,需要你帮助他!

输入

输入的第一行也是唯一一行包含四个整数 n、k、l、m (2 ≤ n ≤ 1018、0 ≤ k ≤ 1018、0 ≤ l ≤ 64、1 ≤ m ≤ 109 + 7)。

输出

在单行中打印满足上述条件模 m 的数组数量。

示例

输入 #1

2 1 2 10

输出 #1

3

输入 #2

2 1 1 3

输出 #2

1

输入 #3

3 3 2 10

输出 #3

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}。