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())
  
  table = [0] * m
  
  
  def calc(init, iter):
      ret = 0
      for _ in range(iter):
          ret += init
          init = (init * init) % m
      return ret
  
  
  ret = x
  cur = x % m
  table[cur] = 1
  for rnd in range(2, min(m + 2, n + 1)):
      cur = (cur * cur) % m
      if table[cur]:
          per = rnd - table[cur]
          persum = calc(cur, per)
          rnds = (n - rnd) // per
          ret += rnds * persum
          ret += calc(cur, n - rnd - per * rnds + 1)
          # print(cur,table[cur],rnd,per,persum,rnds)
          break
      else:
          table[cur] = rnd
          ret += cur
  
  
  print(ret)
  
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"}]