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())
  
  if N == 1 or M == 1:
      print(X)
      exit()
  
  F = (N - 1).bit_length()
  
  A = [[0] * M for _ in range(F)]
  
  for x in range(M):
      A[0][x] = (x * x) % M
  
  for d in range(1, F):
      for x in range(M):
          A[d][x] = A[d - 1][A[d - 1][x]]
  
  S = [[0] * M for _ in range(F)]
  for x in range(M):
      S[0][x] = A[0][x]
  
  for d in range(1, F):
      for x in range(M):
          S[d][x] = S[d - 1][x] + S[d - 1][A[d - 1][x]]
  
  Ans = 0
  depth = 0
  N -= 1
  Y = X
  while N > 0:
      if N % 2:
          Ans += S[depth][X]
          X = A[depth][X]
      depth += 1
      N >>= 1
  print(Ans + Y)
  
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"}]