시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 49 14 12 48.000%

문제

메이지와 리샤는 게임을 하고 있다.

세 바구니에 몇개의 공이 담겨 있는 상태로 게임을 시작한다. 메이지가 먼저 시작하여 서로 차례를 번갈아 가면서, 각 차례에 플레이어는 한 바구니에서 1개에서 $M$개의 공을 가져갈 수 있다. 현재 해당 바구니에 담긴 공 보다 더 많은 공을 가져갈 수는 없다. 어떠한 공도 가져가지 못하는 사람이 패배한다.

게임이 지루했다고 생각한 메이지와 리샤는, 무작위 요소를 게임에 넣기로 하였다. 게임을 시작할 때의 세 개의 바구니는 공이 담겨 있는 $N$개의 바구니에서 중복 없이 선택된다.

메이지와 리샤는 매우 영리하므로, 자신이 이길 수 있을 때는 확실히 승리한다. 리샤가 승리하는 세 바구니 조합의 수를 출력하여라.

입력

첫째 줄에는, $N$, $M$이 공백으로 구분되어 들어온다. ($3 \le N \le 500000$, $1 \le M \le 500000$) 둘째 줄에는, 바구니에 들어 있는 공의 갯수를 의미하는 $N$개의 수가 공백을 사이에 두고 들어온다. 공의 갯수는 $10^{18}$개를 넘지 않는다.

출력

리샤가 승리하는 세 바구니의 조합의 수를 출력하여라.

예제 입력

4 2
2 3 5 6

예제 출력

2

힌트