14555번 - Just as Tic Tac Toe

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

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

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

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

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

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