```go
package main

import (
	"fmt"
)

func mul(a, b [2][2]int64, m int64) [2][2]int64 {
	var c [2][2]int64
	for i := 0; i < 2; i++ {
		for j := 0; j < 2; j++ {
			for k := 0; k < 2; k++ {
				c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % m
			}
		}
	}
	return c
}

func powerMat(a [2][2]int64, b int64, m int64) [2][2]int64 {
	res := [2][2]int64{{1, 0}, {0, 1}}
	for b > 0 {
		if b%2 == 1 {
			res = mul(res, a, m)
		}
		a = mul(a, a, m)
		b /= 2
	}
	return res
}

func power(a int64, b int64, m int64) int64 {
	res := int64(1)
	a %= m
	for b > 0 {
		if b%2 == 1 {
			res = (res * a) % m
		}
		a = (a * a) % m
		b /= 2
	}
	return res
}

func main() {
	var n, k, l, m int64
	if _, err := fmt.Scan(&n, &k, &l, &m); err != nil {
		return
	}

	if m == 1 {
		fmt.Println(0)
		return
	}

	if l < 60 && k >= (int64(1)<<l) {
		fmt.Println(0)
		return
	}

	ans := int64(1)
	baseMat := [2][2]int64{{1, 1}, {1, 0}}
	mat := powerMat(baseMat, n+1, m)
	fn := mat[0][0]
	pow2 := power(2, n, m)

	for i := int64(0); i < l; i++ {
		bit := (k >> i) & 1
		if bit == 1 {
			ans = (ans * ((pow2 - fn + m) % m)) % m
		} else {
			ans = (ans * fn) % m
		}
	}

	fmt.Println(ans % m)
}
```