import sys # 增加递归深度限制，虽然这里主要用迭代，但以防万一 sys.setrecursionlimit(20000) def matrix_mult(A, B, mod=None): """ 2x2 矩阵乘法 如果 mod 不为 None，则结果对 mod 取模 """ a11 = A * B + A * B a12 = A * B + A * B a21 = A * B + A * B a22 = A * B + A * B if mod is not None: return [ [a11 % mod, a12 % mod], [a21 % mod, a22 % mod] ] else: return [ [a11, a12], [a21, a22] ] def matrix_pow(mat, power, mod=None): """ 矩阵快速幂 计算 mat^power """ # 初始化为单位矩阵 result = [[1, 0], [0, 1]] base = mat while power > 0: if power % 2 == 1: result = matrix_mult(result, base, mod) base = matrix_mult(base, base, mod) power //= 2 return result def get_fibonacci(n, mod=None): """ 计算 f(n) 定义: f(1)=1, f(2)=1, f(3)=2 ... 利用矩阵 [[1,1],[1,0]]^(n-1) 的第一行第一列元素即为 f(n) ? 验证: n=1: pow(0) -> I -> [1,0; 0,1]. res=1. f(1)=1. OK. n=2: pow(1) -> [[1,1],[1,0]]. res=1. f(2)=1. OK. n=3: pow(2) -> [[2,1],[1,1]]. res=2. f(3)=2. OK. """ if n <= 0: return 0 if n == 1 or n == 2: return 1 base_matrix = [[1, 1], [1, 0]] # 计算 base_matrix^ (n-1) result_matrix = matrix_pow(base_matrix, n - 1, mod) # f(n) 是结果矩阵的 位置吗？ # [f(n+1), f(n); f(n), f(n-1)] = M^n # 我们计算的是 M^(n-1)，所以得到 [f(n), f(n-1); f(n-1), f(n-2)] # 所以 是 f(n) return result_matrix def solve(): # 读取输入 try: line = sys.stdin.readline().split() if not line: return n = int(line) m = int(line) p = int(line) except Exception: return # 1. 计算 f(m) # 注意：f(m) 可能非常大，作为后续取模的模数 fm = get_fibonacci(m) # 2. 计算 sum = f(1) + ... + f(n) = f(n+2) - 1 # 我们需要计算 (f(n+2) - 1) % fm # 为了防止 f(n+2) 过大，我们在计算 f(n+2) 时可以直接对 fm 取模吗？ # 是的，因为 (A - B) % M = ((A % M) - (B % M)) % M # 所以我们可以计算 f(n+2) % fm fn_plus_2_mod_fm = get_fibonacci(n + 2, fm) # 计算 (f(n+2) - 1) % fm # 注意处理负数情况：如果 fn_plus_2_mod_fm 为 0，减 1 后为 -1，需加 fm sum_mod_fm = (fn_plus_2_mod_fm - 1) % fm # 3. 最后对 p 取模 result = sum_mod_fm % p print(result) if __name__ == "__main__": solve()