거듭제곱

표는 $n + 1$개의 행과 $n$개의 열로 이루어져 있다. 첫 번째 행에는 양의 정수가 적혀 있고, 나머지 $n$개의 행에는 그 수들의 2제곱, 3제곱, 그 다음 거듭제곱 값이 차례로 적혀 있다.

위 표에서 $n = 4$이다. 각 행에는 3, 5, 2, 1의 1제곱부터 5제곱까지의 값이 들어 있다.

대각선에 있는 수(굵게 표시된 칸)를 모두 더한 뒤, 그 합을 $m$으로 나눈 나머지를 구하는 프로그램 power를 작성하라. 예를 들어 $m = 3$이면 9 + 125 + 16 + 1 = 151이다. 151을 3으로 나눈 나머지는 1이므로 답은 1이다.

첫 줄에 양의 정수 $n$과 $m$이 주어진다. 둘째 줄에는 표의 첫 번째 행에 있는 $n$개의 수가 공백으로 구분되어 주어진다.

대각선 수들의 합을 $m$으로 나눈 나머지를 정수 하나로 출력한다.

$n \le 1000000$, $m \le 10000000$이다. 첫 번째 행의 수는 모두 양의 정수이며 100000보다 작다.