CF551D GukiZ and Binary Operations

我们都知道 GukiZ 经常玩数组。 现在他正在思考这样一个问题：有多少个长度为 $n$ 的数组 $a$，其中每个元素都是大于等于 $0$ 并且严格小于 $2^l$ 的整数，使得下列条件成立：？这里，运算符号  表示按位与（在 Pascal 中对应 and，在 C/C++/Java/Python 中对应 &），运算符号  表示按位或（在 Pascal 中对应 or，在 C/C++/Java/Python 中对应 |）。 由于答案可能非常大，请你计算答案对 $m$ 取模的结果。这一次 GukiZ 没有想到解决办法，需要你来帮助他！

输入共一行，包含四个整数 $n$、$k$、$l$、$m$，分别表示数组长度、按位与或条件数字、元素的二进制位数和取模值（$2 \le n \le 10^{18}$，$0 \le k \le 10^{18}$，$0 \le l \le 64$，$1 \le m \le 10^9+7$）。

输出一行，表示满足条件的数组数量对 $m$ 取模的值。

在第一个样例中，满足条件的数组为 $\{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\}$。 由 ChatGPT 5 翻译