ans = []
ans[0] = a
a %= dev
for i in 1..(num - 1) do
  a = a ** 2
  a %= dev
  if ans.include?(a)
    unit = ans[ans.index(a) .. -1]
    unit_times = (num - i) / unit.size
    units_sum = unit.sum * unit_times
    rest_size = num - i - unit.size * unit_times
    rest = unit[0 .. (rest_size - 1)].sum
    ans[i] = units_sum + rest
    puts ans.sum
    return
  end
  ans[i] = a
end
puts ans.sum