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 numpy as np
  
  i8 = np.int64
  
  
  def solve(N, X, M):
      memo_val = np.zeros(M, i8)
      memo_i = np.zeros(M, i8)
      ret = 0
      a = X
      for i in range(1, N):
          ret += a
          if memo_i[a] > 0:
              u = (N - memo_i[a]) // (i - memo_i[a])
              v = (N - memo_i[a]) % (i - memo_i[a])
              ret = u * (ret - memo_val[a])
              nokori = v + memo_i[a]
              for j in range(M):
                  if memo_i[j] == nokori:
                      ret += memo_val[j]
              return ret
          memo_i[a] = i
          memo_val[a] = ret
          a = a**2 % M
      return ret
  
  
  N, X, M = [int(x) for x in input().split()]
  ans = solve(N, X, M)
  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"}]