output_description: Print \displaystyle{\sum_{i=1}^N A_i}.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N X M
attempt: import sys
  
  input = sys.stdin.buffer.readline
  
  n, x, mod = map(int, input().split())
  ans = 0
  temp = x
  num = 1
  # while temp < mod:
  #     temp *= x
  #     num += 1
  
  
  A = [0] * (mod + 1)
  
  # if temp == mod:
  #     A[1] = x % mod
  #     ans += A[1]
  #     for i in range(2, num + 1):
  #         A[i] = A[i - 1] * A[i - 1] % mod
  #         ans += A[i]
  #         # print(ans)
  #     print(ans)
  #     exit()
  
  kouho = {}
  if n < mod:
      A[1] = x % mod
      ans += A[1]
      for i in range(2, n + 1):
          A[i] = A[i - 1] * A[i - 1] % mod
          ans += A[i]
          # print(ans)
  else:
      A[1] = x
      ans += A[1]
      kouho[A[1]] = 1
      temp = A[1]
      for i in range(2, mod + 1):
          A[i] = temp * temp % mod
          if A[i] in kouho:
              migi = i
              break
          kouho[A[i]] = i
          temp = A[i]
      saisho = 0
      hidari = kouho[A[i]]
      saisho = sum(A[1:hidari])
      # for i in range(1, hidari):
      #     saisho += A[i]
      cycle_val = sum(A[hidari:migi])
      # cycle_val = 0
      # for i in range(hidari, migi):
      #     cycle_val += A[i]
  
      cycle = migi - hidari
      kaisu = n // cycle
      amari = n % cycle - (hidari - 1)
      amari %= cycle
      kaisu = (n - (amari + hidari - 1)) // cycle
      amari_val = sum(A[hidari : hidari + amari])
      # amari_val = 0
      # for i in range(hidari, hidari + amari):
      #     amari_val += A[i]
      ans = saisho + cycle_val * kaisu + amari_val
  print(ans)
  
problem_description: Statement
  
  Let us denote by f(x, m) the remainder of the Euclidean division of x by m.
  
  Let A be the sequence that is defined by the initial value A_1=X and the
  recurrence relation A_{n+1} = f(A_n^2, M). Find \displaystyle{\sum_{i=1}^N
  A_i}.
samples: [{"input": "6 2 1001", "output": "1369\n    \n\nThe sequence A begins 2,4,16,256,471,620,\\ldots Therefore, the answer is\n2+4+16+256+471+620=1369.\n\n* * *"}, {"input": "1000 2 16", "output": "6\n    \n\nThe sequence A begins 2,4,0,0,\\ldots Therefore, the answer is 6.\n\n* * *"}, {"input": "10000000000 10 99959", "output": "492443256176507"}]