#include using namespace std; char nl = '\n'; char sp = ' '; using ll = long long; using vb = vector; using vi = vector; using vl = vector; using vvb = vector; using vvi = vector; using vvl = vector; using si = unordered_set; using sl = unordered_set; using tsi = set; using tsl = set; using pii = pair; using pll = pair; using vpii = vector; using vpll = vector; using tmii = map; using tmll = map; using mii = unordered_map; using mll = unordered_map; using pqi = priority_queue; using pqig = priority_queue>; using pql = priority_queue; using pqlg = priority_queue>; using pqpii = priority_queue; using pqpll = priority_queue; #define tp3(T) tuple #define tp4(T) tuple #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define sort_and_unique(a) sort(all(a));(a).resize(unique(all(a))-(a).begin()) #define outrange(x,min,max) ((x)<(min) || (x)>(max)) ll _start_time; #define nano (chrono::system_clock::now().time_since_epoch().count()) #define reset_timer _start_time=nano #define chime cout<<((nano-_start_time)/1e9)< ostream& operator<<(ostream& out, const pair& p) { out << '(' << p.first << ',' << p.second << ')'; return out; } template ostream& operator<<(ostream& out, const tuple& tp) { auto &[t1, t2, t3] = tp; out << '(' << t1 << ',' << t2 << ',' << t3 << ')'; return out; } template ostream& operator<<(ostream& out, const vector& v) { for (auto &i : v) out << i << ' '; out << nl; return out; } template ostream& operator<<(ostream& out, const set& v) { for (auto &i : v) out << i << ' '; out << nl; return out; } template ostream& operator<<(ostream& out, const unordered_set& v) { for (auto &i : v) out << i << ' '; out << nl; return out; } template ostream& operator<<(ostream& out, const map& m) { out << '['; for (auto &[k, v] : m) { out << k << ':' << v << sp; } out << "]\n"; return out; } template ostream& operator<<(ostream& out, const unordered_map& m) { out << '['; for (auto &[k, v] : m) { out << k << ':' << v << sp; } out << "]\n"; return out; } ll n,m,l,k; ll mod; vl merge(const vl& v1,const vl& v2){ int L=v1.size(); vl ret(L,0); for(int i=0;i0) { if((pow&1)==1) result=merge(result,v); pow>>=1; if(pow==0) break; v=merge(v,v); } return result; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m>>l>>k>>mod; m%=mod; vl v(l,0); v[0]=1; v[1]=1; v=fast_pow(v,n); cout<