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: N, X, M = map(int, input().split())
  A = [0] * M
  S = 0
  r = X
  A[r - 1] = 1
  d = 0
  for i in range(1, M):
      r = (r * r) % M
      if A[r - 1] == 0:
          A[r - 1] = i + 1
      else:
          I = A[r - 1]
          j = i + 1
          d = j - I
          break
  r = X
  for i in range(I):
      S += r
      r = (r * r) % M
  if d != 0:
      t, u = (N - I) // d, (N - I) % d
      s = 0
      for i in range(d):
          s += r
          r = (r * r) % M
      S += s * t
      for i in range(u):
          S += r
          r = (r * r) % M
  print(S)
  
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"}]