hyper fibonacci sequence

import math

M,a,b,c,K = map(int,input().split())

​

if K==1:

    print(a)

    exit()

if K==2:

    print(b)

    exit()

​

# 二次元配列作成

nex = []

​

for _ in range(int(math.log2(K)) + 1):

    nex.append([0] * M**2)

​

# 初期化

for i in range(M):

    for j in range(M):

        temp = (pow(i,c,M)+pow(j,c,M))%M

        nex[0][i*M+j]=temp*M+i

​

# ダブリングで表を構築

for k in range(1, int(math.log2(K)) + 1):

    for m in range(M**2):

        nex[k][m] = nex[k - 1][nex[k - 1][m]]

​

A = []

K-=2

for i in range(int(math.log2(K)) + 1):

    if K>>i & 1:

        A.append(i)

​

ans = 0

X = ((pow(b,c,M)+pow(a,c,M))%M)*M+b

for i in A:

    X = nex[i][X]

print(X%M)