题解

矩阵板子，用 python 可以秒。

n=int(input())
p=int(input())
def mul(A,B):
    a00=(A[0][0]*B[0][0]+A[0][1]*B[1][0])%p
    a01=(A[0][0]*B[0][1]+A[0][1]*B[1][1])%p
    a10=(A[1][0]*B[0][0]+A[1][1]*B[1][0])%p
    a11=(A[1][0]*B[0][1]+A[1][1]*B[1][1])%p
    return [[a00,a01],[a10,a11]]
def pow(M,p):
    res=[[1,0],[0,1]]
    while p:
        if p&1:res=mul(res,M)
        M=mul(M,M)
        p>>=1
    return res
if n<=2:print(1)
else:
    T=[[1,1],[1,0]]
    res=pow(T,n-1)
    print(res[0][0]%p)