我们都知道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}。