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: def calc_dynamic(n, x, m):
      # 結果を保持する辞書
      cal_result = {}
  
      # 初期値の設定
      cal_result[1] = x
  
      if n == 1:
          return x
  
      for i in range(1, n):
          cal_result[i + 1] = cal_result[i] ** 2 % m
  
      # return cal_result[n]
      return sum(cal_result.values())
  
  
  def calc_dynamic2(n, x, m):
      cal_result_0 = 0
      cal_result_1 = 0
  
      # 初期値の設定
      cal_result_0 = x
      total = x
  
      if n == 1:
          return x
  
      for i in range(1, n):
          cal_result_1 = cal_result_0 * cal_result_0 % m
          cal_result_0 = cal_result_1
          total += cal_result_1
  
      return total
  
  
  def calc_dynamic3(n, x, m):
      # 結果を保持する辞書
      cal_result = {}
      cal_result_0 = 0
      cal_result_1 = 0
      loop_range = (0, 0)
  
      # 初期値の設定
      cal_result_0 = x
      total = x
  
      if n == 1:
          return x
  
      for i in range(1, n):
          cal_result_1 = cal_result_0 * cal_result_0 % m
          cal_result_0 = cal_result_1
          total += cal_result_1
          if cal_result_1 in cal_result:
              loop_range = (cal_result[cal_result_1], i, cal_result_0, cal_result_1)
              break
          else:
              cal_result[cal_result_1] = (i, total)
  
      if i == n - 1:
          return total
  
      hoge = i
      r = i - loop_range[0][0]
      v = total - loop_range[0][1]
      hoge += r
      total += v * ((n - hoge) // r)
      hoge += r * ((n - hoge) // r)
      # while hoge < n:
      #    total += v
      #    hoge += r
  
      cal_result_0 = loop_range[2]
      cal_result_1 = loop_range[3]
      for i in range(hoge - r + 1, n):
          cal_result_1 = cal_result_0 * cal_result_0 % m
          cal_result_0 = cal_result_1
          total += cal_result_1
  
      return total
  
  
  [n, x, m] = map(lambda x: int(x), input().split(" "))
  print(calc_dynamic3(n, x, m))
  
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"}]