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 solve(N, X, M):
      memo = [-1] * M
      acc = [0] * (M + 1)
      x = X % M
      for i in range(M):
          if memo[x] >= 0:
              break
          acc[i + 1] = acc[i] + x
          memo[x] = i
          x = (x * x) % M
  
      end = i
      start = memo[x]
      cycle = end - start
  
      if N < end:
          return acc[N] + (X - X % M)
  
      cycle_sum = acc[end] - acc[start]
  
      res = acc[start] + (X - X % M)
  
      N -= start
      res += (N // cycle) * cycle_sum
      res += acc[start + (N % cycle)] - acc[start]
      return res
  
  
  N, X, M = map(int, input().split())
  print(solve(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"}]