得到k二进制后，对每一位可取得的方法进行相乘即可，k的二进制形式每一位又分为2种0，1，0时，a数组必定要为一长为n的01串，且串中不出现连续的11，1时与前述情况是相反的。
且0时其方法总数为f(n) = f(n-1) + f(n-2)，其中f(2) = 3,f(1) = 3。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k;
int l,m;
unsigned long long p[];
queue<int> q;
//0: f[n] = f[n-2] + f[n-1]
//1: 2^i - f[n]
struct matrix{
ll a[][];
matrix(){
a[][] = a[][] = a[][] = a[][] = ;
}
void unit(){
a[][] = a[][] = ;
}
matrix operator * (const matrix& p){
matrix ans;
for(int i = ;i < ;++i){
for(int j = ;j < ;++j){
for(int k = ;k < ;++k){
ans.a[i][j] += a[i][k] * p.a[k][j];
if(ans.a[i][j] >= m) ans.a[i][j] %= m;
}
}
}
return ans;
}
};
ll fi(){
//f[1] = 2,f[2] = 3;
if(n == ) return ;
if(n == ) return ;
ll t = n;
t -= ;
matrix ans,p;
p.a[][] = ,p.a[][] = ,p.a[][] = ;
ans.unit();
while(t){
if(t & ) ans = ans * p;
p = p * p;
t >>= ;
}
return ( * ans.a[][] + * ans.a[][])%m;
}
ll quickpow(ll x,ll y){
ll ans = ;
while(y){
if(y & ){
ans = ans * x;
if(ans >= m) ans %= m;
}
x *= x;
if(x >= m) x %= m;
y >>= ;
}
return ans;
}
void solve(){
if(p[l] - < (unsigned long long)k && l != ){
puts("");
return;
}
while(k){
q.push(k&);
k>>=;
}
ll x = fi(),y = (quickpow(,n) - x + m) % m,ans = ;
for(int i = ;i < l;++i){
if(!q.empty()){
if(q.front()) ans = ans * y;
else ans = ans * x;
q.pop();
}
else{
ans = ans * x;
}
if(ans >= m) ans %= m;
}
printf("%I64d\n",ans%m);
}
int main()
{
cin >> n >> k >> l >> m;
p[] = ;
for(int i = ;i < ;++i) p[i] = p[i-]*;
solve();
return ;
}