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 math
  
  N, X, M = [int(s) for s in input().split()]
  
  MAX = M + 1
  sq_max = int(math.sqrt(MAX))
  
  seive = [1 for _ in range(MAX + 1)]
  seive[0] = 0
  seive[1] = 0
  for i in range(sq_max + 1):
      if seive[i] == 0:
          continue
      for j in range(i * 2, MAX + 1, i):
          seive[j] = 0
  
  
  def factor(num):
      factordic = {}
      for i in range(2, min([MAX + 1, int(math.sqrt(num)) + 1])):
          if seive[i] == 1 and num % i == 0:
              factordic[i] = 1
              num //= i
              while num % i == 0:
                  factordic[i] += 1
                  num //= i
          if num == 1:
              break
      else:
          factordic[num] = 1
      return factordic
  
  
  Mdic = factor(M)
  
  # M=G*M2にわける（GはMとXの最大公約数）
  # M2の約数の個数を取得
  G = 1
  divM2 = 1
  for v, k in Mdic.items():
      if X % v == 0:
          G *= v**k
      else:
          divM2 *= (v - 1) * (v ** (k - 1))
  
  # divM2の奇数部分の約数の個数を取得する
  divM2dic = factor(divM2)
  divdivM2 = 1
  for v, k in divM2dic.items():
      if v == 2:
          continue
      else:
          divdivM2 *= (v - 1) * (v ** (k - 1))
  
  
  # Mで割った余りを取得する
  modls = [0 for _ in range(divdivM2 + 35)]
  modls[0] = X
  for i in range(1, divdivM2 + 35):
      modls[i] = (modls[i - 1] ** 2) % M
  
  
  ans = 0
  # 初項から第34項まで足す
  a = [0 for _ in range(34)]
  a[0] = X
  for i in range(1, min([N, 34])):
      a[i] = (a[i - 1] ** 2) % M
  ans += sum(a)
  
  if N > 34:
      if divM2 > 1:
          # 第35項から先は、modGで0になっているはず
          # divdivM2個ごとにループ
          modls2 = modls[34:]
          modls3 = modls2[:divdivM2]
          total = sum(modls3)
          ans += ((N - 34) // divdivM2) * total * G
          ans += sum(modls3[: ((N - 34) % divdivM2) + 1]) * G
  
  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"}]