캔디캔디

택희는 사탕 M개가 들어 있는 상자를 받았다. 이 사탕을 N명의 친구에게 나누어 주려고 한다.

각 친구는 받고 싶은 사탕의 개수를 보냈다. 어떤 친구가 원하는 개수보다 적게 받으면, 받지 못한 사탕의 개수가 그 친구의 부족한 개수이다. 그 친구의 분노 값은 부족한 개수의 제곱이다.

예를 들어 어떤 친구가 32개를 원했는데 29개를 받았다면 부족한 개수는 3개이고, 분노 값은 3^2 = 9이다.

각 친구에게 줄 사탕의 개수를 정해 모든 친구의 분노 값의 합을 최소로 만들 때, 그 최솟값을 구하시오.

첫째 줄에 사탕의 개수 M (1 ≤ M ≤ 2×10^9)과 친구의 수 N (1 ≤ N ≤ 100,000)이 주어진다.

다음 N개의 줄에는 각 친구가 받고 싶어 하는 사탕의 개수가 하나씩 주어진다. 각 개수는 2×10^9보다 작다. 친구들이 받고 싶어 하는 사탕의 총합은 항상 M보다 크다.

친구들의 분노 값 합의 최솟값을 2^64로 나눈 나머지를 출력한다.